Are Newton's laws always an approximation because of the non-existence of inertial frames?

To specify, Newton's law are in any case an approximation for $| vec{v} | << c$ of Einstein's special relativity laws. Since in special relativity the idea of inertial frame is crucial, too, the question remains.

The point is that this laws are mathematically valid without approximation in the precise conditions by which inertial frame are defined. So it's always about find situations that are very very close to the ideal ones, to test the effects predicted by the theory. Then it's not the theory that is an approximation, because precise ideal conditions in which it works are defined.

It's the finite precision by which phenomena can be observed and ideal situation can be created that have to approximate well ideal conditions. Otherwise, it could be argued that Pitagora's theorem is only an approximation since right triangle doesn't exist (it's impossible to draw a perfect right triangle). Whereas it's the draw that is an proximation of the ideal one. So are not theoretical abstract theories that are approximations of the reality, it's the reality that can be observed only as an approximation of them.

Newtons law hold in inertial frames, now due to their Non existence then is it that Newtons law are always an approximation ?

Not really. One issue is the multiple meanings of the term “inertial frame”. Some people, when they use the term “inertial frame”, refer to a physical system of clocks and rulers that can be used to assign coordinates to physical objects and events. Other people (including myself) refer to the mathematical coordinate system as the “inertial frame”.

One advantage of the second approach is exactly the issue you raise. While we may not be able to get an inertial set of clocks and rulers, we can simply attach accelerometers to the clocks and rulers we have and directly measure their deviation from inertial. Once we have done so then it is a simple mathematical operation to obtain an inertial frame.

Newton’s laws can be formulated and applied in that inertial frame (coordinates) regardless of the fact that the clocks and rulers involved are not themselves inertial.

Now, although this is not the issue that makes them an approximation, Newton’s laws are approximations in three other senses: First, all laws of physics are approximations. Second, Newton’s laws approximate relativity in the limit of sufficiently low speeds. Third, “perfect” is an essentially meaningless designation in physics and “accurate to within experimental precision” is sufficient for physics.

First, ANY physics law (or any "law" in science in general) is an approximation that has its very own applicability field. It doesn't matter if the science has reached the important milestone to know better (as it happened with Newton physics and Einstein relativity).

Newton laws can be extended to non-inertial frames using only purely mathematical trics. So yes, they are defined for an inertial frame, but are used in non-inertial frames as well without losing any bit of accuracy. They just don't look that simple as in an inertial frame.