Is there a simple relationship describing the kinetics of air evolving from water on heating?
There is no simple relationship. The problem is that you can't heat the water absolutely uniformly. Thus all the convection currents in the water would create a mathematically chaotic relationship. There is also the problem of the water being supersaturated - especially if you heat from the bottom.
Is it fast or slow compared to a reasonable heating rate?
This would seem to be sort of a judgement call, but I'd say that it would be faster to dissolve a gas in a liquid (say via bubbling) than heating to expel it. The bubbles mechanically stir the solution rather than just equilibration by diffusion from the surface. Also think of liquid nitrogen. It boils so fast when spilled on the floor that the drops skitter around. The escaping gas insulates the liquid drop limiting the heat transfer to the liquid. So there is a limit as to how fast you can heat a solution.
Does it depend on just how far the system is from equilibrium
Yes. The further from equilibrium, the less likely a solution could be super-saturated.
Conditions like the amount of air-water surface boundary
The time to reach equilibrium surely depends on the surface area to volume. Think of a cylinder of water. A cylinder which has water one inch deep would certainly come to equilibrium faster than cylinder of the same diameter which has water a mile deep.