I second tfong007's suggestion. If your rides are fairly short, then buy something that connects to your laptop (DeLorme GPS LT-20 / 99$) . I find it works great as a last minute resort. If you want something more dedicated (and more expensive), then look at a dedicated GPS unit that plugs into a cigarette lighter. If you get NeverLost almost every time, that's 10$-12$ a day. After about a month the GPS will pay for itself.

I've done a similar thing with a Sirius receiver. I typically rent cars for a couple of weeks or longer, so having my own Sirius receiver solves the problem of paying expensive Sat radio fees and I have the content I want. Worked great when I had an Avalon and now for the Impala.