You could try using the Overpass API, this uses Open Street Map data. I'm not sure if it will do exactly what you are after but it may be a start.
The call below searches for cities. The bbox creates an area to search within. The example I have created below uses coordinates that surround Portsmouth, UK.
http://overpass.osm.rambler.ru/cgi/xapi?node[place=city][bbox=-1.150818,50.761653,-0.987396,50.851908]
The results returned from this provides some useful data
<?xml version="1.0" encoding="UTF-8"?>
<osm version="0.6" generator="Overpass API">
<note>The data included in this document is from www.openstreetmap.org. The data is made available under ODbL.</note>
<meta osm_base="2013-04-11T23:39:03Z"/>
<node id="17721995" lat="50.8065249" lon="-1.0744016">
<tag k="is_in" v="EnglaHampshire, England, UK"/>
<tag k="is_in:continent" v="Europe"/>
<tag k="is_in:country" v="United Kingdom"/>
<tag k="is_in:country_code" v="GB"/>
<tag k="is_in:county" v="Hampshire"/>
<tag k="name" v="Portsmouth"/>
<tag k="name:ru" v="Портсмут"/>
<tag k="name:sr" v="Портсмут"/>
<tag k="place" v="city"/>
<tag k="population" v="197700"/>
<tag k="url" v="http://www.visitportsmouth.co.uk"/>
</node>
</osm>
I do believe it is possible to replace the coordinates with other search functions such as a country name.
EDIT:
http://overpass-api.de/ with query base address http://overpass-api.de/api/ (4 cores, 64 GB RAM).
http://overpass.osm.rambler.ru/ with query base address http://overpass.osm.rambler.ru/cgi/ (8 cores, 64 GB RAM).
Both servers have a total capacity of about 1.000.000 requests per day. You can safely assume that you don't disturb other users when you do less than 10.000 queries per day or download less than 5 GB data per day.