Have a look at Mappero and ModRana. I am not sure if they will satisfy all your requirements, but I depend on them (more on ModRana) when I plan oversea road trips. As both will cache maps for offline used, they worked very well for me as long I stay within the planned path (if I don't have access internet). The work around is to pre-download a larger area of the offline maps before you take off for the trip. And you have a rather large list of open maps to choose from (including Google maps).