Nutrition-wise? Creatine supplements can increase chances of heat stroke, so eating tons of beef, etc., might have a similar effect.

You do want to stop if feeling any nausea.

A fan by itself can work pretty good when you're sweating.

Can you not alter your workout time to when it's cooler? Say early morning? Or do something inherently cooler, like swimming?

I am having a similar issue. Thanks to the wonderful American economy, I have been stuck working at a greenhouse wholesaler for over a year now. From September through April, it's a pretty easy job with doing prep work, working in the lab, filling pots, moving stuff, etc... You leave work with adequate energy levels and you can bring intensity to your work-outs. But starting in May, the busy season starts and your schedule gets thrown to the wolves and exercise is a luxury. Now, we are dismantling some greenhouse to be replaced, meaning I am lifting heavy shit all day and this week it was 90+ and clear skies all week. I got one work-out in this week and that's been it.

I feel guilty not going to the gym or sticking to my triathlon training (not paleo I know but I'm doing it barefoot!) but paleo fitness is about adaptation. Life is hard and sometimes kettlebell snatches just have to wait. If you kill yourself at work and THEN do a hard intense work-out in the heat, what are you doing to your body? Especially because I'm not sleeping the 8 hours a day I should be. So my recommendation is adapt. What is your living situation like, as in where do you live? Do you live near the woods? Hiking may not be as intense as lifting rocks but there usually are rocks abound in the woods :o). You can adjust the intensity based upon the temp. Do some Erwan LeCorre MovNat stuff outside. Do you run at all? I've started barefoot running recently and that can be a bit easier to deal with in terms of heat. Are you close to a swimming hole? Not only is swimming a great work-out but it has a ton of real world practicability. How do you feel about yoga? If you can find a good instructor for a decent price, yoga can help with your mobility and flexibility if done right AND they probably have AC. If you can't afford a class, spend some time working on your flexibility and mobility on your own. Do some short, intense work-outs (maybe no more than 20 minutes, if that) and take some time outside to really work on opening your hips and chest and stretching your hamstrings.

You know the old saying, "When life hands you lemons, you paint that shit gold". Grab a paintbrush brotha.

I am pretty sure our ancestors were changing physical activity in relation to weather conditions. We have to listen to our bodies, and working out is about getting fit and healthy, so anything that might cause your health to deteriorate is not welcome. I am pretty sure that hunter-gatherers were spending a lot of time chilling in a shade trying to move as little as possible when it was the hottest. Unnecessary and possibly dangerous overuse of energy supplies.

We are better equipped to survive physical activity in a heat than other animals (bless the sweat!), and there are still hunters who run after an animal for hours in a heat till the animal gets a heat stroke. we can deal with it better... BUT the risk of heat stroke is real and you have to take it easy. Go shorter, lighter... maybe less high intense cardio movement and more slower strength workout. you may want to have a wet towel ready to put it cold on your head/neck to cool down a bit.

just a thought, no real science to back this up:

Workout intensity is what drives adaptive responses, and it is a relative thing. If heat and humidity increase the intensity, it could be that the hormetic response remains the same, even though the weights you lift are lower.

So exercise until you feel the same kind of fatigue (+/- same kind of training intensity). Keith Norris at http://theorytopractice.wordpress.com/ talks about this kind of thing and calls it autoregulation (although I don't remember him using this principle with heat)

(Edit: speaking of the devil, Keith Norris just posted this about autoregulation, good stuff!):

Make sure you're drinking enough water, I'd say. Don't eat so much directly before the work out. My work outs are usually only 20-30 minutes long, and it's been near 100F for the past two weeks here. My weights are in my garage, which has no air-conditioner or fan. I'm drenched within a minute or two, but I'm starting to enjoy the challenge and the extreme nature of it all. I'd say stick it out, unless you're working out for a long period of time, or you feel like you're going to pass out. Again, and obviously, make sure you're drinking enough water.