Maybe Nokia might be interesting for you. I suppose they still ship free offline navigation with their newer phones. (Google Maps requires an online connection, although by now you can apparently cache some small parts of the map in advance).
I'm not sure Nokia would be right for him, though- I have a (Samsung) Windows Phone and the e-mail is great, but it's not a Gmail client.