I'm an adventure guide. I currently work (outside, without AC, sleeping in a tent mon-fri) in North Carolina (the heat index was 126 two days ago!) and have worked in Dubai and Oman (where the temp hits 110 by April and 140 in August)
Here are a few things I do:
1. wear a BIG hat. a big dorky old lady hat. It keeps your face in the shade :)
2. keep something like a bandanna handy that you can soak and wear. the evaporation cools you off
3. stay in the shade. Find a space in the shade with a little breeze
4. get low. dig a hole and sit in it, get under a rock. the ground is cooler than the air
5. get in deep water. jump into a large body of deep water. it will be cooler than the air. watch out for rocks and sharks
6. lay around during the hottest part of the day
7. use an insulated water bottle. it will keep even water out of the tap cooler longer. add ice if you can
8. drink water constantly. like a gallon a day.
9. wear breezy, lightweight, light colored, fast drying clothes that have long sleeves. sounds hot but trust me. your skin will be in the shade.
10. Also, an umbrella is a great way to take shade around with you! Make sure your umbrella is opaque and a dark color.
11. If you know you're going someplace without shade, take a silver (yes SILVER) tarp with you. You can set up a tarp using some tent stakes, rope and poles or vehicle or any large object (boulder, hill etc) On the beach we set up tarps with kayak paddles as poles and rope. Blue/orange/green tarps let too much light in and essentially turn into an oven. Silver stops the light from coming through to create real shade.
In the United Arab Emirates, the traditional buildings have these weird towers coming up from the middle. The tower has openings like windows on all four sides at the top and bars running across them. I asked about them when I was there last. Turns out they used to wet cloth and hang the wet cloth from those bars. The tower was high enough to catch a breeze. The wet cloth would cool down the air, which would fall downward. The main seating/living area of the home was situated beneath the tower to make life bearable. AC before AC was invented! You can utilize this in your house. Moisten a t-shirt or a pillowcase and use clothespins to put it over a floor fan.
Also in UAE, everything opens really early in the morning, like around 6:30 or 7, and closes from 11 to 3:30 and then opens up again from around 4 till 10pm. No one does anything during the hot part of the day. Too bad the hot parts of the US can't switch to that schedule.