we arent confined to state park usage. about 70% of Arizona is public land/forest/blm
do you plan on staying in Phoenix at all? I cant imagine staying in town, as you would be trespassing on someone's land if you tried.. we dont have any parks here in town that would allow you to hang. The great part tho is that you can drive for an hour in any direction and find whatever you need. I have a nice mountain range just 35 miles away that can get me into the 5-6'K range in less than 1 hour.
If you already know the route you plan to drive on your way to SLC, then use hikearizona to map out a hanging itenerary.
another thing: riparian areas hold the best chance of hanging in the desert. Once you leave the valley of the sun you will be heading north into the forests.
here's a neat factoid about AZ: average overall elevation is 4,100 feet.

here's the site: www.hikearizona.com