modRana provides navigation/routing features also. It uses Google Directions for online routing. Good thing is that you can do the routing while you are online, download the map tiles along your route and then go off without the need of staying connected to net. You can choose from various map tile providers - Yahoo, Google, Open Street Map, Virtual Earth and others few.
If you install 'espeak' it can do quite usable voice navigation in multiple languages too (if you don't mind robo voice). But don't expect it to pronounce local non-english street names properly, although I can say it is still usable.