If you're looking for a rental, enterprise and hertz order their pickups without hitches so people can't tow. I think all of the Toyota Tundras have hitches though. i'm pretty sure all of the LARGE suvs have class two or three tow hitches. That should be good enough to get all four wheels off of the ground with an auto transport from uhaul or something. Kinda pricey though, but you'll get better mpg than a uhaul truck and be comfy.
I've also used uship.com once before. It was great for me but i hear its hit or miss.
If you can get unlimited mileage in your state drive around and find a full size pickup with a hitch and drive out to az to get the car. That'll save some $$$. But don't crash it, and keep it a little while to to make the mileage seem reasonable.