Does the photon mediate electromagnetic interactions? We first hear that the photon is a gauge boson that mediates the electromagnetic interactions. Then that two electrons exchange a virtual photon. And finally that virtual particles don't exist, but are an outdated concept used only to describe Feinmann diagrams. So... if virtual particles don't exist and there are no virtual photons, then what exactly mediates the electromagnetic interactions? What exactly do two electrons exchange when they repulse?
 A: The interaction between charged particles is described by a theory called quantum electrodynamics, which is itself part of a large theory called the Standard Model. Both of these belong to a class of theories called quantum field theories.
The issue of whether virtual particles really exist (they don't) has been discussed to death and I don't think it's worth trying to add to that here. Suffice to say that the interaction between charged particles can be expressed as a sum of integrals called propagators that are modelled as the exchange of particles including photons.
When we quantise the electron field we find that in order to preserve a symmetry called local gauge invariance we have to include the photon field as well. That is, the theory requires both electrons and photons to exist. In this sense photos do mediate the interaction between electrons. In principle electrons also mediate the interaction between photons, though photon-photon scattering is so weak that it has yet to be experimentally observed.
Now, from here things get a bit more philosophical and woolly. You ask:

then what exactly mediates the electromagnetic interactions

It's very tempting to ask of physical theories but what is really happening but that type of question rarely makes sense. A quantum field is not a physical object. It is an operator field i.e. a field whose value at every point in spacetime is a mathematical function. Quantum field theory works very well, and indeed it is notoriously the most accurate theory ever constructed. Since quantum fields are mathematical constructions they presumably describe something physical, but it is not clear what that is or even if the question what they describe has any physical meaning.
A: Let us start from the beginning of the SU(3)xSU(2)xU(1) standard model of particle physics. SM. This is based on these elementary particles:

These particles have each unique quantum numbers which identify them, and also a specific mass, and we can consider them as  measured data ( how is another long story, suffice that their existence depends on data). Measurements have told us that there are four fundamental forces. The group theoretical structure of the SM (also a distillate of observations and measurements) prescribes how interactions happen.
The SM prescribes quantum field theory as the tool to calculate interactions between these elementary particles , and this tool leads to Feynman diagrams which are a shortand for integrals in a perturbative expansion of the solution. Each fundamental force in QFT has a coupling constant associated with the interaction.
Here is the simplest diagram for electron electron scattering:

The internal line is called a photon because it has the electromagnetic couplings entering the integral, it transfers a four momentum between incoming and outgoing ( dp/dt is the definition of force) and has all the quantum numbers of the photon except its mass, which is off shell. It is the carrier of the electromagnetic interaction in this simplest lowest order diagram. Electromagnetic interactions can be carried by other "virtual" particles as here:

where an incoming gamma produces a pair of e+e-in the field of a nucleus with a virtual  electron exchange and a virtual gamma from the nucleus. This again is a prescription of an integration over the limits of the variables, and the electron and gamma are off mass shell.
So the photon is involved in electromagnetic interactions, but not only the photon, all charged elementary particles couple  electromagnetically and mediate electromagnetic interactions. The photon ( and generally the red column in the particle table) are important in the lowest order diagrams in the expansion of the QFT solution into Feynman diagrams , depending on the interaction. 

So... if virtual particles don't exist and there are no virtual photons, then what exactly mediates the electromagnetic interactions?

There are virtual particles by mathematical definition, as there are  integrals and differentials. It is the coupling constants that separate electromagnetic from  the  other interactions.

What exactly do two electrons exchange when they repulse?

Momentum and energy and quantum numbers , and it is the quantum numbers that define the particle name of the exchange, the off shell mass is not important because mass is not a conserved quantity.
