What special properties of magnetic fields allows Faraday's law to work? Faraday's law states that as the magnetic flux through a loop of wire changes, an EMF is induced around the wire that is proportional to the rate at which the total flux through the loop is changing...
But of course the wire cannot directly measure the flux inside the loop.  The electrons in the wire can only be affected by fields in the wire.  There must, therefore, be an alternative formulation of Faraday's law that integrates around the loop instead of across the surface that it bounds.
This is easy to imagine if field is constant and the loop is moving.  From the motion of the wire and the flux vector at every point on the wire, you can determine how much flux is entering or leaving the loop at every point and sum them up to get total $d\phi_B/dt$.  In fact the EMF will be the sum of the Lorentz forces.
But how does this work if the loop is stationary and the flux is changing arbitrarily?  We can imagine divergenceless fields that pass through the loop, but do not intersect the loop at all.  If such fields were to wax and wane in place, then no integration around the loop could possibly evaluate the changing flux.
So...  such divergenceless fields must not be possible.  There must be some further constraint on the structure of magnetic fields that lets the flux change be calculated with a line integral.  It must be possible to derive the sum of the amount of flux entering of leaving at every point from the flux vector and its derivative alone around the loop.
What, exactly, is that constraint on the structure of magnetic fields, and what is the line integral formulation of Faraday's law that it enables?

Progress:
Some answers below mention this intuitive picture of "field lines" that we draw for ourselves, and assert that these lines cross the loop of wire as the field changes.
That implies that the field lines move.
Motion, though, is not really a property of the field, so why is it a property of these imaginary lines that we draw?
I've certainly seen animations of a waxing dipole field, with field lines moving out from the center into space as the field strength increases.  The line density indicates flux density, and those lines definitely would cross a loop of wire as those answers below suggest.
I haven't yet figured out if the number of imaginary line crossings is a linear function of the local properties of the field, but I have figured out why that animation makes sense for dipole fields.
Given a dipole field at the origin, so:
$$
\vec B(\vec m, \vec x) = \frac{3\vec x(\vec m \cdot \vec x)}{|x|^5} - \frac{\vec m}{|x|^3}
$$
... where $\vec m$ is proportional to the dipole moment, we find that
$$
 \vec B(\vec m, \vec x/\alpha) = \alpha^{3}\vec B(\vec m, \vec x)
$$
i.e., a bigger dipole field is the same as a stronger dipole field.
So imagine that we made a 3D model of a dipole field with many field lines, at a density proportional to flux density.  We put an imaginary loop near this model, and then we gradually scale the model up by 2.
As we scale this model, field lines will cross the loop.  By the equation above, if we had scaled a real dipole field up by the same amount as our model, there would be 8 times as much flux passing through the loop.  The scaling, though, has moved our modeled flux lines farther apart, reducing their overall density by a factor of 4, so there are only 2 times as many modeled lines passing through the loop.
In the net, as we scale our model up by a factor of $\alpha$, the result is an accurate model of multiplying the field strength by a factor of $\alpha$, with lines crossing any loop at a rate that sums up proportional to $d\phi_B/dt$.
Since real magnetic fields (and maybe all divergenceless fields?) are summations of dipole fields, we can accurately model a field using field lines that expand outward from, and collapse inward to, the dipole centers.  Since the dipole centers for the fields around magnets and coils are all inside the magnets and coils, this makes sense intuitively and visually.
For the kinds of strange fields I was wondering about above, that could be zero everywhere along a loop of wire, for example, the corresponding dipole centers would be spread out through space, and imagining lines that emanate from them or collapse into them would be very difficult.

Resolution:
I see now that the magnetic field doesn't need to have any special form, other than being divergenceless, because the EMF around a closed loop just isn't determined by the local properties of the magnetic field.
The line integral form of Faraday's law (for a non-moving circuit) is just:
$$
\mathcal E=\oint\frac{\partial \vec A}{\partial t}\cdot\mathrm d\vec l
$$
where $\vec A$ is the magnetic vector potential, of which $\vec B$ is the curl.  This can just not be expressed in terms of local properties of B, i.e., without integrating over space.
I was fooled by the idea that the "field lines" we imagine are representative of the magnetic field only, and that they should move according to changes in their own local properties.  But it turns out that if you want to animate the field lines in order to represent a changing field in such a way that the number of lines crossing loops reflects Faraday's law, then the velocity of those lines needs to be
$$
\frac{\partial \vec A}{\partial t} \times \frac{\vec B}{|\vec B|^2}
$$
(and this can probably be simplified using some vector calculus identities that I don't know).
The calculation of $\vec A$, and these velocities, requires an integration over space of some sort.  In retrospect, I suppose this is not surprising -- since each line represents a constant amount of flux, then the position of the nth line will be determined by an integration of flux over space, no matter where you "start" from.
Thanks to all those who helped.
 A: This is a perceptive question and therefore it has an instructive answer. I thought I would add a physical picture to adorn the answer already provided by Dale.
The equation $\nabla \cdot {\bf B} = 0$ tells us that lines of $\bf B$ have to run in closed loops. They never start or stop at any point. So we can always get intuition about $\bf B$ fields by imagining that we have in our possession a huge number of loops, each closed and can never be opened, but each one can stretch as far as we like. For the purpose of imagination you could imagine them as if they were made of some material and you could hold them in your hand. Each loop has a sense of direction, indicated by little arrows marked on it.
Now to provide the magnetic field at some location, you have to provide a sufficient density of field lines, so you do it by taking some of these loops, stretch them out and arrange them so that you have lines running in the same direction at the place where the field is non-zero. Elsewhere your loops will be curving over and coming back around, of course.
Finally, to make the field at some location change, you can change the density of the lines there, or change the number of lines, or both. If you only change the density but not the number then you won't change the net flux. Such a change will not generate an e.m.f. by Faraday's law. If you change the number of lines, then you will generate an e.m.f., and as Dale points out, because the lines are always parts of closed loops you can never thread a new line in like sewing with a needle and thread. There is a topological constraint. You have to change the number of field-line loops that are linked with the ring where the e.m.f. appears. And to do that, something right there at the ring has to take place: the magnetic field-line has to pass across the ring. Electromagnetic effects are indeed local, like pretty much all of physics (and as the question correctly insists).
The connection between this local nature and the fact that one can state Maxwell's equations also in their integral forms is also fascinating, and worth thinking about. For example it never ceases to impress me that I can deduce how much charge is enclosed in a sphere by measuring the electric field only at the surface of the sphere. This might seem like action at a distance, but it is not. It is because there is a differential equation which the field satisfies everywhere.
When we learn geometry we find it interesting but not too surprising that the circumference of a circle has a fixed ratio with its diameter. But as physicists we should think about that: how come when the diameter is larger the circumference gets larger by just the right amount? How does it 'know' to do that? After all, the circumference is wholly located at positions away from the centre. There must be a differential equation which the distances in question are satisfying everywhere. And there is! It is Einstein's field equation.
A: The formula for the EMF is
$$\mathcal E=\oint_C\vec E\cdot\mathrm d\vec l$$
Where $C$ is a closed curve and $\mathrm d\vec l$ is an infinitessimal vector along that curve. An important result from vector calculus is Stokes' theorem. It says that the line integral of a vector field around a curve can be related to a surface integral of the curl of that vector field:
$$\oint_C\vec E\cdot\mathrm d\vec l=\iint_A(\nabla\times\vec E)\cdot\mathrm d\vec a$$
Here $A$ is any area which has $C$ as its boundary, $\nabla\times $  is the curl and $\mathrm d\vec a$ is an area element perpendicular to the area. The fact that we can choose any area as long $C$ is the boundary is quite amazing. This is also fundamentally the reason why you are confused about this.
We can then apply the Maxwell Faraday equation 
\begin{align}
\nabla\times\vec E&=-\frac{\partial \vec B}{\partial t}\\
\implies\mathcal E&=-\iint_A\frac{\partial \vec B}{\partial t}\cdot\mathrm d\vec a
\end{align}
Using the fact that EMF is defined as $-\frac{\mathrm d\Phi}{\mathrm d t}$ we arrive at the definition of $\Phi$ that you're used to
$$\Phi=\iint_A\vec B\cdot\mathrm d\vec a$$
As a final note Stokes' theorem is essentially the fundamental theorem of calculus,
$$\int_a^b f(x)\,\mathrm d x=F(b)-F(a),$$
but extended to two dimensions. Here $F'(x)=f(x)$. The fundamental theorem of calculus is equally impressive/confusing: we can integrate something over a domain and the result only depends on the value at the boundaries. The reason we can do this is because the derivative of $F$ is defined everywhere.
So the special properties of $\vec B$ are

*

*$\vec B$ is continuous and has a derivative everywhere

*$\vec B$ obeys the Maxwell Faraday equation

Actually I'm not sure if these are all the required properties but I hope that makes it clearer.
A: 
But how does this work if the loop is stationary and the flux is changing arbitrarily? We can imagine divergenceless fields that pass through the loop, but do not intersect the loop at all. If such fields were to wax and wane in place, then no integration around the loop could possibly evaluate the changing flux.

Integration of magnetic field couldn't, but integral of induced electric field would. In case of stationary loop, EMF is due to induced electric field in the loop.

So... such divergenceless fields must not be possible.

No. They are possible, theoretically. This happens for example when the loop is put around infinitely long solenoid with alternating current. Magnetic field outside the solenoid (and thus also on the loop) vanishes, but EMF need not to, because induced electric field does not vanish outside the solenoid. So induced EMF, in accordance with Faraday's law, is connected to changes of magnetic flux, but this change does not need to happen anywhere close to the loop. It can happen anywhere that influences the total flux, like inside the solenoid.

There must be some further constraint on the structure of magnetic fields that lets the flux change be calculated with a line integral. It must be possible to derive the sum of the amount of flux entering of leaving at every point from the flux vector and its derivative alone around the loop.

That is not a common way to think about change of flux. And it would be hard to make it general, as seen in the above example, where no magnetic field is present in the loop.
Instead, it is more common to express the flux through the loop as line integral over the closed loop of the so-called vector potential $\mathbf A$ in the loop:
$$
\int_S \mathbf B \cdot d\mathbf S = \oint_C \mathbf A\cdot d\mathbf l.
$$
This vector potential can be derived from magnetic field but not easily. It is much easier to find magnetic field from the vector potential. The simple differential relation is
$$
\nabla \times \mathbf A = \mathbf B.
$$
A: You don’t need an alternative formulation of Faraday’s law, just the inclusion of Gauss’ law for magnetism as well. That law implies that you can describe the magnetic field in terms of magnetic field lines that form continuous loops. It is that property which resolves the issue you consider.
Specifically, the only way for the flux through the inside of the loop to change is for a magnetic field line to cross the wire. If we try to increase the flux by avoiding the wire then we inevitably have a line that goes through the inside of the loop twice, once in each direction. Such a line contributes no net flux, it cancels itself out.
The only way to change the amount of flux inside the loop is for a field line to cross the wire. It is that crossing of the wire that induces the EMF. As it crosses the wire, there is no need to imagine any remote influence. What affects the EMF occurs only at the wire itself.
