Atom interferometry tests of universality of free fall based on the differential measurement of two different atomic species provide a useful complement to those based on macroscopic masses. However, when striving for the highest possible sensitivities, gravity gradients pose a serious challenge. Indeed, the relative initial position and velocity for the two species need to be controlled with extremely high accuracy, which can be rather demanding in practice and whose verification may require rather long integration times. Furthermore, in highly sensitive configurations gravity gradients lead to a drastic loss of contrast. These difficulties can be mitigated by employing wave packets with narrower position and momentum widths, but this is ultimately limited by Heisenbergs uncertainty principle. We present a novel scheme that simultaneously overcomes the loss of contrast and the initial co-location problem. In doing so, it circumvents the fundamental limitations due to Heisenbergs uncertainty principle and eases the experimental realization by relaxing the requirements on initial co-location by several orders of magnitude.