Storing all the worlds map data locally is unnecessary. All you need is to let the user download the maps for the part of the world he intends to visit before he leaves. If it's a licensing problem I'm sure it can be solved with money. I'll happily pay a reasonable fee for each additional country/region.
I don't think the licensing problem can be solved with money. TomTom owns the mapping data and obviously wouldn't let Google provide a navigation app since it would put them in direct competition with TomTom. That's why Google had to create their own maps for the US.
The map downloading model you're describing already exists and there are already plenty of other companies providing in-car GPS devices for that. I don't think it's appropriate to implement that sort of thing in a smartphone since the entire point is that it should always be connected.
