Free Geographical Database Of All Countries (Over 8 Million Places): GeoNames
GeoNames is a set of free and downloadable geographical databases of all countries which includes over 8 million place names.
The data comes in tab-delimited + utf-8 formatted text files and can be downloaded as a whole or per country.
Besides the locations of the places/cities/countries, databases include supplementary data like capitals, statistics, timezones and more.
GeoNames data can also be reached from their free webservice which can return results in XML and JSON.