Luckily OsmAnd+ (cost £5, there's a free version) is brilliant, and having all of the maps loaded into the phone at once is so much better than having to download bits of maps as you go along. It navigated me around Japan faultlessly last January.
Edit: just downloaded the full version, and I can confirm it's a lot better than every other Osm apps I've tried. I'm using a Galaxy S4 by the way
Edit - here is their git repository: https://code.google.com/p/osmand/
Edit: Just tried it now and I can zoom out to the whole of Tokyo (and in fact wider) no problem.