The solution I use is TrekBuddy. I have been using this app for the past 5 years in various platforms from Java to Symbian to Android.
This app can load offline map and show your (GPs) position on it. It can show and record your trail (as GPX) and you can show predefined way points on the map (using GPX again). Being a free project from beginning, it does not have a great documentation and support.
In spite of all these downsides, I can still vouch it as one of the most useful and most powerful GPS-Navigation-Tracking app. It requires a bit of learning curve and some serious homework, but that comes at the benefit of using the navigation with out Internet connection.
There are quite a lot of documentation, tools and How-Tos in wiki style in their home page.
I have been using this app for my trekking, city navigation and touring. Few capabilities of this app are:
- Display a previously downloaded map tiles and over lay current GPS position on it.
- Show the trail as an overlay on the map.
- Display previously defined way points on the map
- Display previously defined route on the map.
- Play a sound when the current position is with in a given radius of a way point
- Log the entire trail as GPX
- Switch between various maps
- Available for Java, Symbian, Android, BlackBerry phones
Display statistics like average speed, average moving speed, altitude change, number of satellite seen etc as seen in the following image:

- All the above without Internet connectivity
- All the above free.
PS: I am in no way associated with TrekBuddy other than I am using it and amazed by its usefulness, which you would have probably guessed by now ;-)
There are other apps like OSMAnd, which can do the above with AND without Internet connection. Few features will not work without Internet connection, but all that you asked will work.
Official Google maps now allows pre-downloading map tiles. With this you can select an area which you would be visiting and download them when you are with WiFi connection. However there are no way you can record the route. For that you may have to use MyTracks app from Google.