If you know the country then you could use the new address service:
http://www.geonames.org/maps/addresses.html#address It is available for 17 countries so far and includes most of the information you need. The elevation is not yet included. For the elevation you can reduce the credits usage when you combine many lat/lng in one call. In particular if they are nearby the credits usage will be smaller.
findNearbyPostalcode never has a street name. You could first call OSM and if it does not include a postal code you can then call the postal code service.