As Newtons laws of motion only hold in inertial reference frames, how come we use them freely to describe motion of particles under the influence of gravity? Isn't the only frame where we can apply Newtons laws in a frame accelerating at the same rate and in the same direction as gravity?
We can use Newton's Laws in non-inertial reference frames if we consider the action of ficticious forces. Indeed, in General Relativity the frame in free-fall is inertial and the one at rest relative to the ground is non-inertial. But we can use Newton's Laws if we consider the ficticious force: gravity. This is the same thing that happens in the accelerating elevator: we may use Newton's Laws in the elevator frame if we consider the ficticious force field that arises from the equivalence principle.
Inertial reference frames are frames where bodies with zero net force move at constant velocity. It follows from this definition that inertial reference frames have constant velocity with respect to one another. Measurements in one inertial frame can be converted to measurements in another by a Galilean transformation.
If one reference frame is being accelerated you can no longer use a Galilean transformation, and you must include ficticious forces that act on masses whose motion is described using a non-inertial frame of reference.
I think that your confusion comes from the fact that what we usually call "laboratory frame" is in the Earth's surface, so it suffers a gravitational force. However, remember that a normal force is also acting over the objects over the surface of the Earth, so the net acceleration is zero.