I think the thing to do is focus on the aspects of Kingdom-building that are fun. I doubt your characters are that interested in finding a particular stonemason. Break it up into a series of adventures and skill challenges. THings for the characters to do:
Explore and map their holdings (one of the first things to do). Be ready with a lot of random monsters, many of which they will need to run from. Determine where they want to build their stronghold and secure that area. Secure a route back to civilization (gotta keep those supply lines safe). Design the stronghold in its various stages. It's gonna have to start out as a small fort, most likely. Let them find a few ruins that could be refurbished. This step will be gleeful fun for some players, and others will want nothing to do with it. Let them do this in their downtime. Plenty of adventures will involve expanding the safety zone of their territory. Let them do the first few on their own, then hand wave a few as they are more powerful and have some soldiers that can accompany them. Things that will be an actual challenge should be run as a normal adventure. Make alliances back in civilization to hold on to their positions. Be sure, as soon as they have tamed the wilds, any number of challengers will be along to wrest control away from these common upstarts.
Remember, you can break this up, with gaps of several years between adventures. Periods of strife with longer periods of building and politics. Downplay the parts your player's aren't into. Perhaps the Heroic tier will be the taming of the land, while the Paragon tier will be somewhat political, defending their lands from opportunistic nobles.
I'd recommend trying to adapt John Wyck's Houses of the Blooded RPG, specifically the Seasons rules to handle your nation building (actually this was a plan of mine as well).
Houses of the Blooded has a very streamlined, fast and effective nation building mechanic (as I said before) called Seasons. It would need some tinkering, but using some of the basic ideas in a D&D campaign could be really fun. Best news is, the Game book is available online and I think I paid only 4 bucks for it. Even on my tight budget that was reasonable enough.
Skill challenges sound like a great idea, I ought to be able to vet a lot of stuff through the skill challenge. There are a couple of other areas I have concerns about. For example, someone has to run things while they run off and handle a small battle over in a tiny corner of their kingdom. So they'll need someone to run the day to day affairs. I'd really like to make that a more personal experience than a skill challenge (I roll to see if he's trustworthy. Now I roll to see if he's loyal.) Roleplay will certainly be a big part of that, but I'd like to to do more than boil down into successes vs. failures.
After all, the PCs will decide when they've found someone they want to hire. I don't want them to engage in the Find a Castellan skill challenge followed by the Hire the Castellan skill challenge and as of now, skill challenges are designed to end when the PCs make a decision. I suppose I could make judging individuals (and finding them, and recruiting them) all skill challenges, but it seems a little obtuse. The PCs may find that, mid way through the recruiting of the NPC that they would prefer a different NPC for castellan. So... they drop the skill challenge mid challenge? It's like walking away in the middle of a combat because the monsters in the other lair seem more interesting. Powers, actions, time, and investments on their parts wasted.
I guess I mean, skill challenges have a specific ending. You succeed or you fail (generally meaning there's a penalty). But if the part chooses a third ending (We go look over here) then it sort of deflates. I'd like to have some soft mechanic for dealing with nation building that I could use in sequence with skill challenges.
I don't think you need a second system to manage your nation. Sure, you can look to other systems for inspiration, but the mechanics of 4e are such that if you use them cleverly they should be more than enough.
One thing I'd suggest right off the bat is to rethink the role of skill challenges. Instead of having a separate challenge for each task undertaken in pursuit of a goal, make the pursuit of the goal itself the challenge. Let the players choose the tasks they want to undertake, and make each task a relatively short sequence: two to four checks is good. If they abandon a task, discard some or all of the successes and failures gained during that task.
For instance, your Find A Castellan skill challenge could be reinterpreted as a subtask of a Manage Your Keep challenge. The PCs can try to manage it themselves, making a number of boring and time-consuming checks, or they can look for someone to do the work for them. Again, they can do this any way they like: they could ask around with Streetwise to find someone good for the job, they could hold interviews and select the best applicants with Insight, or they could contact somebody else's castellan and try to convince him to come work for them instead.
If they abandon a task in the challenge, they might lose all of that task's successes, or they might be able to salvage some of them if they manage things right. The someone-else's-castellan might be unwilling to work for you, but if you think to ask he can direct you to someone else who might be interested, saving you the trouble of looking for him. The PCs might reject all the interview applicants, only to overhear one of the applicant's drivers make a comment that demonstrates exactly the kind of insight needed for the job; all they need to do to win the challenge is to offer him the job.
Or heck, they could ignore the challenge entirely. That's just like running from a fight; they don't gain the experience, and they're likely to suffer the consequences of inaction. A crisis arises in their absence, creating a new challenge: Resolve the Crisis. If they keep slacking off, the situation continues to worsen until it's dealt with.
Another neat thing you can do is to keep skill challenges dynamic, with no fixed endpoint. When the challenge feels like it's been overcome, count up the number of checks made and use that number to set the reward. If your players are really into a challenge, extend it for as long as it holds their interest; if the solution turns out to be simple, let the challenge end.
Make a general rule for yourself that a skill challenge can't be failed any more than a combat encounter. The individual tasks making up the challenge can be failed, of course, but the only way to permanently "lose" is to give up and abandon the challenge.
Some challenges might not have any end, like Manage Your Keep or Curry the King's Favour. Instead, your number of successes represents a way of "keeping score"; outside influences can affect your score, requiring continual effort to maintain your position. Experience is awarded after each task, instead of at the end of the challenge.
e.g. in Manage Your Keep you might automatically lose 1d3 (on an exploding die) successes each month. If your successes drop below 0, your lands are officially in crisis. Your castellan can make one check every week in your stead, and with his 80% success rate he can usually handle all your affairs on his own. However, if the dice happen to explode multiple times you may have to take matters into your own hands to deal with the situation.
e.g. in Curry the King's Favour your score represents the king's opinion of you, similar to an affiliation score in 3.5. You can undertake tasks (whether assigned to you or by your own volition) to change the king's opinion of you or another courtier--this can include anything from a dragonslaying quest to a smear campaign. At the same time, your enemies will be intriguing against you; if their checks are successful, they reduce your score and/or increase their own. In addition, you might lose a flat amount if you neglect your lands or other duties.
I could go on, but hopefully you get the idea. Use the good parts of the skill challenge system, and ignore the stuff that doesn't work for you.
I think I see what you're talking about (and it sounds very nice) but let me be sure I caught it all.
You have a Manage Your Keep Skill challenge that requires X successes before Y Failures. You then have a number of smaller skill challenges: Find a Castellan, Import Materials, Acquire Good Architects, Manage Labor, etc, etc. When you succeed at one of these skill challenges, it counts as a success towards the Manage Your Keep skill challenge (and when you fail). If you don't find good architects and manage your labor, the best Castellan and materials won't help.
Layering skill challenges like tree branches, that's a very brilliant suggestion.
I think I know how I'll manage it then, at least a good portion of it.
There will be 3 tiers, each with a sliding bar.
1. Heroic Reclaiming Your Nation _*______________________________ Small Large
As they complete quests and make alliances with the local creatures, the bar will push along. The party has until Paragon to get it as high as they can. Depending on how far they got in Heroic, they will have different troubles in paragon. If they only make it to 20%, then they have a very small kingdom that the wild inhabitants will try to take away. On the other hand, if they control 90%, there will only be a little reclaiming to do, but some greedy neighbor seems them ripe for the picking. The degree to which they Reclaim determines what they can draw on in the Build Your Nation/Paragon phase.
2. Paragon Building Your Nation _*______________________________ Pathetic Paragon
With their kingdom reclaimed, the heroes now try to build up their nation either by reclaiming more land, improving it's infrastructure, and providing it's populace safety against other threats. How well they build their nation in Paragon will determine how much support it can offer against invaders in Epic. If they have a relatively pathetic kingdom, they will have very little support in Epic, but fewer people will lust after its sovereignty. However, even a small paragon kingdom will offer them better things. A large paragon kingdom would be the prize jewel of the land, ensuring that others will want it for their own. While a pathetic kingdom would have a great deal of internal danger (revolutions, uprisings, riots) a paragon kingdom would face stronger external threats (other nations, terrible monsters, united savages). It will really determine how refined their Epic threats will be.
3. Defend Your Nation _*________________________________ Sovereign Conquered
This is the final chapter. Although they can still build up their nation and what not, this is the tipping point at which war comes to their kingdom. The PCs rise to destiny will be a bloody one, fraught with the battles of safeguarding their little country from internal or external threats. In the end, it will determine how they are remembered by the coming generations.
I think that in subsequent tiers, they can still effect the previous tier's scale, but it will be far less efficient. So while making a pact with the local dwarven community in Heroic will increase their Reclaimation Slide by (making up a random number here) 10, doing it in Paragon will only bump it up by 5. Of course, having dwarven smiths available to you would naturally increase your Building Slide.
there are definatly some good ideas, I have always run these types of games as follow
Prolog: The pc do quest or whatever and end up with the rights to the land maybe gain a lvl
Intro: The pc travel to the land they now own and set up a small base maybe bring a small caravan with them say 3 wagons that contain a merchant wagon who buys stuff from the pc and sells them basic supplies although at a slightly higher cost since he is the only merchant around, A wagon for cupplies for the camp, tents food, and other similar junk, and a wagon for a handfull of hired guards. Perhaps the guards are highered with promis of free housing once the area is settled properaly could even be a minor quest to gather the merchant and guards. gain anouther couple lvls.
Beginning: The pc's start getting the lay of the land, find a more permenent place for the camp *probably wherever they find that is the safest and has water and decently defendable. They map out the area close locating caves identifing wildlife and problem area. At this point the players will probably have to run from a lot of the encounters while exploring and clearing out some of the most minor things. This should take up a couple more lvls
Main: now the PC have a base camp, a idea of what area they can handle and what areas they need to avoid and for the most part are still under the radar of the monster tribes and most of the areas inhabitents. They should also be about lvl 5 and starting to be able to handle themselves in the ruff wild. Next to start clearing out the area for the rest of heroic teir they should go on a large number of quests to clear out small monster dens, explore and clean out ruins and treasure sites. delv into the beginnings of the deaper caves and make minor contact with the monster tribes in the area. By the end of heroic teir they should have amassed a stockpile of usefull supplies and a small hoard of gold (give a much larger treasure handout then normal they will need it)
Intermission: Having made a dent into the wilds and leaving the heroic teir they should have garnered the attention of the local tribes while still to small for the larger tribes to take notice. They should also be ready to head back to the cities to restock, the merchant will probably be ready for a trip back so they can escort him and leave the guards to watch the camp. While in the big citie let the players buy new magical gear rituals and a ton fo supplies have them purchase everything they thing they will need for a while. They will also need to hire some more guards and a few other usefull npc to further expand the camp, I would use skill chalenges to find the npc but otherwise use a TON of rping. Possible important npc could be a cook- with a increase in guards and people in camp it will be needed. some hunters though the guards could also do this but by this time the pc should be beyound hunting and ready for others to do that. also maybe a few scouts to help keap a eye of the newly cleared land as well as watch for threats. Some workers to help expand the camp diggers a mason probably like 25 assorted workers and anouther wagon full of guards. while in town they might also come acrost some less then freindlies like muggers bandits theives as well as other would be adventurers who claim to have right to the land. I would have them at least meet a few people who have claims to the land some with good rp should be able to be converted to freindly npc while others should be down right hostile but keap conflict simple still. With rp rewards skill chalenges and small skirmishes in town should be anouther lvl or 2 then the pc having what they need should return to base camp.
The return: back with fresh supplies and a bunch of extra help they are ready to search for a more perminent location, they probably have already found a ideal place but if it is so perfect then other monsters will probably have already claimed the spot Time to evict them. this should take a lv or so
Main part 2: With the site picked out the camp can be moved and construction of more perminent dwellings can begin. Let the players have as much or little say in the designe as they want also they can use the old monsters village to give a good beginning for there own fort. For now things in the fort can be mostly automated unless the players wish. a lot of what needs to happen in base is pure rping maybe a few skill chalenges and junk the players main concern now is the growing attention of other monster tribes. Do the players convert or enslave the monsters or simply slay or run them off. Also with there base growing larger monsters will beginn to take note. The players should set off to take on these chalenges. below I will list a few possible chalenges that they will need to adress
Larger monsters will still be very dangerouse to the players and may start to couse the players some trouble
Monsterouse tribes, Goblins orcs gnolls and other such monsters who have tribes/villages/ camps in the area will probably start to feal threatened by the players and eather try to make peace, test the players or outright attack the players and maybe even the camp giving chance for some grand battles while the players deal with them, both defence battles to defend the camp and offence ones to take out enimy villages.
Vandals: others claiming to own the land start to couse trouble bribing guards or monsters, vandalising camp or dounright attacking the party. Lots of rp and other possibilities.
Basicaly there are tons of chalenges that the pc's can overcome while the fortress slowly expands and grows into a small village, also while all this goes on let the players designe how the village looks and map it out as it grows, maybe add a few features every game. maybe even take a few trips back to town to recruite more guards and hire more npc again finding npc should be handled with a mix of rp and skill chalenges over all there should be more then enough to close the gap to near lvl 20.
Conclusion: With the fort in place and the area mostly cleared and settled. the new task begins clear out the largest of the monsters and begin settling the matter of polotics, what kingdon does the land belong to or do they start there own kingdom, what about the last few claims on the land how do we get rid of them kill the owners buy out the claims give them a small bit of the land. what about the naboring kingdoms how do they react to the new changes, are they happy to see it settled do they like the pc or try to remove them. the remainder of the lvls should invold cleaning up the rest of the land maybe some larger scale battles with naboring kingdoms and kings/nobls who think the pc should pay taxes. also a lot of rp potential on how they deal with the demands and desires of the people who move to live there maybe even a few more quests to encurage people of note to move. Also while doing this they will enter into the erpic teir so they should start looking at what path they will take and how that path will effect the town/land they now have. perhaps even as they retire you can start new chars to further settle the lands **kids or NPCS of note that might start adventuring or who might inherite the town and other such people would be perfect so this game could potentialy spann over many generations of chars developing huge areas of land that will forever live on in the game and your players minds and hearts.
This is for the most part how almost half of my gaming world was developed even almost half of my current pantheon is now made up of player chars who retired into devinity or who were high enough and well made enough that I made them gods after they retired.
anyhows this is all just my take on the style game u described. a lot of what goes on in the building of the fort I would ignore, maybe quests for special material and junk but besides the parts that are abnormal like special npc and stuff I would simply let other inhabitents slowly move in and the npc left at camp steadily build it up while the pc give them direction. Stuff like building materials civilians and otherwise boring menial details I would leave in the background of the game to keap them from taking the joy away. While special building materials to make that fortress even more memorable and impregniable and spcial features like maybe a rare plant that is known to extend natural life span or other such things would be perfect things for the pc to worry about
If you kept up with me this long congrats and I look forward to your responce if you didn't well sorry my typing sometimes drags on a bit