Currently, I'm using my own service. I got a dump of data (free) from geonames.org. GeoNames also offers a web service, but it gets hammered a lot and your request can time out. If you make your own service you'll have to do some pretty complicated math in order to calculate the closest city/state/address based on the lat/lon coordinates. You'll need a web server and a database to offer your own service. Google isn't the only one offering reverse geocoding though, there are plenty of others (Microsoft offers it, as well as many 3rd party companies that ONLY do reverse geocoding). It's best to just do some research on the topic and figure out what works best for you and fits into your budget.
However I changed my code to use the reverse geocoder in 3.0 and it works much quicker. You can charge for apps that use the 3.0 reverse geocoder (provided by Google) as long as that isn't the only purpose of the app (like I said, read the 3.0 TOS on the topic on the dev portal). If you can wait until the summer to release your app, I'd suggest using the stuff already built into 3.0. Makes things a lot easier.