I'm answering my own question.
Apparently this is one of those rare cases when the physicist must doubt what he observed -- or what he thought he observed -- and believe the numbers his theory yielded instead.
From further experiments I've noticed that the ice tends to form thin plates inside the supercooled water once the crystallization process starts -- this form of ice is apparently called dendritic ice. When the starting temperature of the water was about $-10^\circ$C, the resulting ice-water mixture still contained a lot of water by the time the process finished, and most of it was trapped between those thin ice plates. The latter fact would make it hard to measure the mass percentage of water exactly.
I've found some scholarly articles studying this process -- mostly in the context of formation of ice plugs in pipes. In [1] they measured the temperature at a number of points inside a capsule full of supercooled water during ice formation. From the time-dependent temperature profiles in the article it is obvious that my model above (that energy released by the freezing ice heats up all of the water and ice) is completely wrong. The process happens so fast (at a rate of a few cm/s, depending, among other factors, on the temperature), that the heat transfer between the already frozen (thus heated to $0^\circ$C) and still supercooled regions is practically negligible.
However, based on the observation that ice and water appears well mixed in the already frozen region, we can put forth a new model: the released latent heat of fusion is used up locally and quickly in the boundary layer of the expanding frozen region. As a particular region at the boundary freezes, it heats up rapidly to $0^\circ$C (or close to it), and heats up the water surrounding it. Since the ice plates thus formed are relatively close to each other, the resulting region containing ice-water mixture will mostly be free of temperature inequalities, and those inequalities that do exist will be damped quickly. Therefore the thermal profile of a volume of supercooled liquid undergoing freeze-out will consist of two flat regions, with a relatively sharp boundary between.
It would be quite interesting to look at the process with a thermal infrared camera. Such an observation could confirm or reject the model above. To my knowledge, no one published such an observation -- if such a publication exists, I'd be very interested in seeing it. A video made by such a camera would be especially enlightening.
With some simplifying assumptions (spherical container full of supercooled liquid with uniform temperature, and a single nucleation source at the center), the simple model above could be made quantitative, but I haven't done that yet.
1 Juan Jose Milon Guzman, Sergio Leal Braga: Dendritic Ice Growth in Supercooled Water Inside
Cylindrical Capsule, 2004
Yes the core will warm gradually.
Heat transfer in a solid is conduction.
Ice has a known thermal conductivity and will have a linear temperature profile from all paths from surface to center. There will be concentric rings of constant temperature at all times.
It would be impossible to warm just the surface and not warm up the molecules next to the surface.
Surface will warm to $32^\circ\mathrm{F}$ ($0^\circ\mathrm{C}$) and by that time the temperature profile will be established.
The surface at $32^\circ\mathrm{F}$ ($0^\circ\mathrm{C}$) will just migrate inward. The surface will not go above $32^\circ\mathrm{F}$ ($0^\circ\mathrm{C}$) as ice simply melts. As you migrate inward the temperature slope will remain constant. As the path becomes shorter the core temp will increase.
If you raised the temperature up to $30^\circ\mathrm{F}$ ($-1^\circ\mathrm{C}$) and held it there for a while the core would raise to $30^\circ\mathrm{F}$ ($-1^\circ\mathrm{C}$).
Think about a cutting torch on metal. Once you get the surface to melt it just cuts right through the rest.
Best Answer
As a supplement to @tpg2114's answer, it also depends on the "wetness" of an object.
As most people should know the evaporation of water requires energy and this lowers the temperature.
The lowest temperature a wet object can reach is what is called the "wet-bulb temperature." This can be several degrees lower than the "dry-bulb temperature," the amount can vary depending on the humidity (specifically atmospheric pressure). If that wet-bulb temperature gets below 0°C, then freezing is possible.
In order for said wet object to get close to the wet-bulb temperature, some convection needs to occur in order to take that evaporated water away (i.e. wind).
This is one of the ways wind under a bridge can cause freezing under the right conditions. Another possible reason might be heat lost by radiation
or the earth via conduction.