Our app, Geopointe, does have this built in. In addition to doing all the mapping you might want, we have an Apex method at geopointe.API.getDistance(Id1, Id2, geopointe.API.units.MILES). This gives you back the distance.
That will be far and away the simplest in the end.
If you want to write a method yourself, checkout the MapQuest Open Street Map API at http://open.mapquestapi.com/sdk/js/v7.0.s/mqa.toolkit.js. That's just a bunch of JavaScript, but do a find on "Util.distanceBetween" and you'll see a function that accepts 2 lat/lon objects and does some math. It's not too hard to reverse engineer.
You can also do a find for "arcDistance" in that toolkit. This is a method measuring the distance, but takes into account that we live on a sphere.
If JavaScript is ok for you, you can also checkout the MapQuest Open APIs. See http://developer.mapquest.com/web/documentation/open-sdk/javascript/v7.0. There are no major limits, especially since you already have lat/lon data. You don't even have to show a map. You could just use it to do the Calcs you need.