I believe that you are not being coherent.
As far as I know, you can only choose to treat gravity on either a non-relativistic regime, where you totally neglects any relativistic effect, and thus you have newtonian gravity, or you have to use the full machinery of GR. I believe that there is no 'Special-Relativistic gravity' or 'Semi-Relativistic gravity'. In the case of newtonian gravity you would specify on the instantaneous positions, but because of the regime that you are on, that is not a problem in itself.
If you particles can even have the chance to move on a time-step faster than light, you have long departed the regime of validity of newtonian gravity, so, it's not the implementation that is wrong, but the modeling of the problem.
In the case of EM you have that Maxwell's equation are covariant with respect to lorentz transformations, so there should be no problem if you use covariant equations for the source $(\rho,\vec j)$.
I don't know. That is a very good question, but my first thought is that since gravity couples to the full Stress-Energy Tensor, and the idea to get newtonian gravity is to do $T^00 \approx \rho c^2 $ and the rest you ignore, this surelly fails when you have relativistic speeds, even though the metric could be safelly aproximated.
I believe that you should be able to to something like retarded potentials + gravitational radiation corrections, but I really didn't do the calculation so I'm not going to go on speculating.
About the Coulumb x Liénard–Wiechert potential. Yes, this is the first idea, but as far as I remember what happens is that you have a bunch of point charges, you calculate their LW potential, then you apply that potential on something else, but you don't calculate the back reation of the target on the source. Also, I don't know if you can readly extend the LW potentials to non-point charges, but I believe not.
@Ruslan, thanks for noting the typo