My 60D has never experienced overheating, even shooting in direct sunlight in 35 degree celcius weather.
The 60D is only a few dollars more than the T4i at the moment so is most likely still within your budget. The T3i also has much less overheating issues than the T2i, though I cannot personally vouch for it, only going off what I've been told or read.
I would suggest you get either the 60D or T3i over the T4i; it does not add any really useful features for video - the continuous AF is pretty useless, and even the touch focus feature is not acceptable for use while recording.
If you're worried and it's in direct sunlight, it's easy enough to put an umbrella, or some kind of other sun shade. Probably a good idea anyway, as the heat might cause additional sensor noise and not be good for the battery.
The T4i AF is not super fast, but it is far better than nothing. It also works with the new STM lenses for faster and quiter AF as compared to a normal EF or EF-s lens.