Such a generator would work similarly to the Random Character Generator. It wouldn't bother with coming up with specific statistics (such as "how many people live here"?), since that wouldn't work well with the Wiki software and those details are massively setting-dependent anyway. Instead, it would come up with random entries from specific categories - see the Random Character Generator for how it works for a different application.
So what needs to be done is to come up with (a) specific categories which represent the basic building blocks of the generator, and (b) come up with and write different entries within these categories. Here are some ideas I have so far:
Government: In this entry, the random generator would pick one of a large number of different government types. I have created a list of different government types here, which is based directly on a list given by a Wikipedia entry - but for the generator to work, these must exist as distinct entries. Furthermore, this list only covers real world forms of government - and there is no reason why we shouldn't add forms of government from fantasy and science fiction, such as "Magocracy" or "Hive Mind".
Dominant Terrain: This would expand on the Terrain page. Users could use tabs (like with the Random Character Generator) and select how many predominant terrain types they would like to have for their nation (let's say from one to five). However, the number of terrain types listed in the wiki is still rather limited, so new entries for terrain need to be written as well.
Trade Goods: After that, we need to figure out the economy of the nation. For this, we need entries for all sorts of different industries. This page of the CIA World Factbook is probably a good starting point. However, substances from mythology and fiction - including various types of Phlebotium - need to be added as well (how about Orichalcum?).
Religion: I think there should probably be two sub-categories for religion. One is the overall form of the predominant religion(s) - Shamanism, Monotheism, etc.. I haven't yet found a good page for all those different types, but this might be a good starting point. The other sub-category should list specific divinities or other powerful entities which are worshiped - the Mythological Characters page should be a good starting point for this. Note that these entities don't need to represent the actual deities of the setting - just something you can base your own creations on.
What other categories should there be in such a generator? And more importantly, who would be willing to help me out with it and write entries for it?