Supongo que en un breve futuro Google Maps Navigation tendrá la posibilidad de ser plenamente funcional sin necesidad de conectarse a internet. En ese momento sólo tendremos que planear nuestra ruta, descargar los mapas con una buena conexión y salir de viaje sin acceder a internet.
Mientras ese instante no llega, aquí dejo los pasos que seguí: