You don't need any virtual photons but you can derive Coulombs law w/o using perturbation theory. It's most transparent in
a) Coulomb gauge or in
b) A°=0 gauge plus fixing of the residual symmetry of time-independent transformations respecting A°=0.
In both cases it boils down to construct the inverse of the Laplacian 1/Δ; in Coulomb gauge this is due to the Poisson equation