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
[tex]\Delta A^0 = \rho[/tex]
with
[tex]\Delta^{-1} \to k^{-2}[/tex]
in k-space and
[tex]\Delta^{-1} \to |x|^{-1}[/tex]
in x-space
This results in an interaction term
[tex]V \sim \int d^3x\,d^3y\,\frac{\rho(x)\,\rho(y)}{|x-y|}[/tex]
Of course there are other interaction terms involving physical (transversal) photons as well.