Populating this may be your initial problem, but I would think there are some DB's out there that already have something like this as it's done over and over and over.
Any decent relational DB will laugh at these small queries if the DBs are setup even half decent.
I mean, build country list, on change, select states/province based on country, build that list, on change, select city/town for the state.
This is trivial for PHP/(insert db here whether it's postgresql, mysql, mssql, etc...)
As far as populating, I bet if you look hard enough, there are lists you can easily construct something or parse it with PHP and make an insert script to your DB, once that's done, querying is cake.