This is a great idea.... and I think if you combine it with other ideas shared on this thread, you could get a tribal-themed City Construction Challenge.
I think it should be done in stages, like the City Construction Challenge, perhaps with required buildings later on.
I also like the idea of the hunter/fisherman huts.
How about combine this with the tree spirit challenge (link:http://www.minecraftforum.net/topic/336073-challenge-the-tree-spirit/ )
for every x amount of log you must have a sprite there to keep the tree together and for a home they require water, sunlight (a hole in the ceiling of the hut letting light in) and nourishment, any organic material that's not part of your tree will do. Or drop the sprites and just have a tribe and be a tree spirit at the same time.
completely on related to what I said above, you could have gods and you sacrifice to them food, people, structures, items for goodies ( like a god "blesses" your crops by giving you bonemeal)
and/or so the gods don't harass you with disease, hunger, and other things. To do this you'll have to invedit items, throw things into the bonfire (or even better have a special sacrificial alter made with cactus, fire or lava). To sacrifice people you subtract 1 from your population and throw whatever your using to show one of your people (like the pumpkin on a fence) in to your sacrifice thing. To chose what the gods do take any mythology you like and build on that, you can also use gods literature and movies etc. as well. Or make up your own gods.
With 1.1 update your people can be villagers spawned from a spawn egg. Snow golems can be people too.
If trap sheep in a pen using fence next to a hut and put some shears in to a chest then one of your people becomes a shepherd giving you X amount of wool per day, one shepherd can herd up to 4 sheep (more sheep more wool) if you get more then 4 sheep you'll need more shepherds.
If a tamed wolf is put in to a hunter's hut it will increase 1 food to a hunters gain. Wolves take up one space in a hut, but can be placed in a dog house which is a simple structure with a 1x1x1 inside in which a wolf is put, it must be next to a hut. A wolf must be a pet of one of your people, a person can only have one wolf, and you can have one wolf for yourself. It's best to have your hunters own the wolves but other villagers can have one to.
At the first or second age you can be allowed to mine surface iron for buckets, flint&steel, and shears
i like to keep track of my progress using note pad Example:
made first house (room for 3 more people)
got some food (2 apple. food for 3 more people)
made work bench and furnace
found coal (5)
found iron ore (8)
smelted iron ore (8)
no one was born today
Other idea: Gnome settlement,
Same idea only you live underground and your villagers are gnomes (trolls, dwarves what ever) which means they eat ore instead of food. The most basic source of "food" is coal which feeds one gnome, you can also feed one gnome a 64 stack of stone. Iron feeds 5 gnomes, gold 10, 2 redstone can feed one, lapiz feeds 5 obsidian feeds 15, as well and diamond feeds 20. Gnomes can't eat charcoal because it's organic. To make a home for a gnome you must hollow out a 3x3x3 room and put in a furnace and 2 half slabs for a bed. Gnomes fear A) the sun so keep your settlement deep underground and B ) flora so keep them away from things organic, you can't put anything wooden inside the settlement as well as mushrooms,grass, flowers etc. this means torches are not allowed use lava glowstone or burning netherrack. But you can give them tools, and put chests and some other little things. You are not a gnome so you can go outside, and use wood etc. or you could install dwarvencraft and never go to the surface. building an extension to a gnome room and putting a cobble genarater(how do you spell it?) with a chest full of picks will give you X amount of cobble a day.
I did this challenge, and it does make it more interesting with the different foods being worth different things, for example I did that an egg feeds 1 person, a fish feeds 1 person, a salmon feeds 2 people, etc.