I had this problem a while back and did exactly what adam suggested:
- Download the database of cities from geonames.org
- convert it to a compact lat/lon -> timezone list
- use an R-Tree implementation to efficiently lookup the nearest city (or rather, its timezone) to a given coordinate
IIRC it took less than 1 second to populate the R-Tree, and it could then perform thousands of lookups per second (both on a 5 year old PC).