Android - How can I geo-tag a photo after I've taken it?
Actually I found such an app, after a fair bit of searching.
Photo Geolocator (Google Code)
Currently you can't look up locations via an address, so it only really works for nearby locations, but that's still better than having to edit images on a PC, IMO.