GraphHopper also stores the street names and the lookup is easy: ala graphHopper.getLocationIndex().findClosest(lat, lon).getEdge().getName()
GraphHopper runs on Android too, but you'll have to develop a full app on your own. There is currently only a rather raw demo for Android.
Oh, I didn't recognized that every blog entry is displayed on the main site and other will read this stub entry :)
And yes, thanks for the wiki link ;)