"Sort by distance" using only "City and State", but missing both "Postal code" and "lat/long"

How can I Sort by Distance when most of my nodes lack a postal code and lat/long??

---

I have a lot of locations with City and State (Country=US). But I don't have postal codes or lat/long coordinates.

Now, it's a simple task for me to go in an edit a particular node, edits is location, and use Google maps to look up a lat/long for any one specific node, and save it in the lat/long fields of the node's location.

However, given the number of nodes, it's not feasible for me to do this by hand.

---

One way to solve this would be to (somehow) go through my locations table, find all the relevant nodes, somehow lookup the lat/long, and then store those coordinates. The advantage of using this method is that each location only has to be geocoded only once, and the resulting lat/long can be stored for future reference.

The other way would be to do this at view time-- somehow look up lat/long and compute distance based just on that. This is nice in that it doesn't force me to alter my data by arbitrarily storing a very approximate lat/long in my location, which might get confused if some of my nodes already had more-exact lat/long stored in them-- exact lat/long would be indistinguishable from "rough guess" lat/long. (although this isn't a problem I personally face right now). Another advantage of doing it at view time is that the location_views code is closely tied in with all the geocoding stuff, so perhaps it would be easier on me to implement.

But best of all, however, would be some approach that has already been done, but which I haven't heard about yet.

--

Any suggestions on how I could accomplish this?
Thanks in advance!