The Open Place Database (OPD) will contain information about places and administrative boundaries for the entire world including how they changed over time. The data will be licensed with the Open Database License (ODbl) so that it can be used by anybody in any way that they please. There is an API for light programmatic usage with the option of installing OPD yourself for heavy usage.
We've only been working on this for three days, so there's much more to come:
Regularly updated data dumps
Much more data (at the time of writing we only have data for US counties)