In electromagnetic induction, what force is actually doing the work?
For a wire that isn't moving, it is the electric force that does the work.
What physical force actually drives the electrons around the circuit?
If there the circuit is moving, the magnetic force can also contribute to the EMF, the work comes from the $\vec B$ field diverting the electrons which allows the electric field of the protons pulling it back. When the circuit is staying still, it is 100% entirely the electric force doing the work.
Let's say we have a coil and an increasing magnetic field through the loop. The electrons start to flow by faraday's law. Is there a very real electric field that is induced around the wire which does the work?
The electrons start to flow because of the electric field (the protons are prevented from moving the opposite direction because of atomic and molecular forces, the lattice merely gets strained overall instead of a flow of protons). The electric field is very real.
Also, why do the charges even start moving in the first place?
They were already moving because of thermal motion, but there was no average motion, the nonzero average motion develops in the first place because of the electric field.
At each instant in time, there is some instantaneous value for the magnetic field.
Sure, but there is also a curl of $\vec E$, and the curl of $\vec E$ is related to the change in $\vec B$, so if there is an expanding region where $\vec B$ changes, there is also an expanding region where there is a nonzero curl of $\vec E$.
The magnetic field cannot cause the electrons to start moving because it doesn't affect stationary charges
When there is zero average net velocity for the electrons, then the $\vec B$ field does zero average net force (if the $\vec B$ field changes a great deal over a region small enough where you don't get good averages this might fail but there are likely electric fields in those regions, so the magnetic effects are small unless the charges are moving quite fast). But it isn't the $\vec B$ field itself, but only the changing $\vec B$ field that is related to the circulating electric field. Back when and where the $\vec B$ field changed, the electric field was circulating. And since then there was an expanding sphere where the $\vec B$ field changed and everywhere that the changing $\vec B$ field went, the circulating electric field did more than follow, it was there at the exact same time. So back when the $\vec B$ field changed somewhere, there had to be a circulating electric field, and they propagated together ever since. The circulating electric field arrives at the same time as the change in $\vec B$ field arrives.
Once a current starts to flow, there is a net velocity and so a net magnetic force is possible, this separates the mobile electrons from the stationary protons, and the resulting electric fields from the charge separation can do work.