Esas enormes bases de datros que mencionas, son la respuesta a tu pregunta, en algún momento el Servicio que mencionan en la siguiente página era gratuito, pero creo que ya no
http://www.codediesel.com/tools/free...tion-api-tool/
De todas maneras te puede dar una idea de como encarar el problema.
Fijate, aquí encontré otro aparentemente gratuito
http://www.geoplugin.com/webservices/php
mira el detalle de los resultados, ahi apenas ubicas el pais, cuanto mas detalles posea la base de datos mas datos podrás extraer.
Saludos