I have a Nokia 500 3G phone for this purpose. It costs just 119€ without the contract, unlocked and everything.

Small, 3.2" screen, fast enough, can do GSM/3G (850/900/1800/1900/2100) and WiFi. Get a local prepaid SIM and you can have a Personal Hotspot, too.

The maps for 95 countries around the world are free (Nokia owns Navteq) and one can download them to the phone in advance.

I'm not 100% sure if route guidance still requires data connection for the route or if that is offline, too. I usually don't need navigation but just to know where exactly I am.