Kill the king- Each civ, including the player, has a "King" unit that is immune to marksman. Civ ceases to exist after king dies and all cities and units turn barb.
Usually called Regicide I believe - it was in at least one of the scenarios in a Civ 3 expansion, with the Shogun unit upgradeable at certain techs so you had to choose between risking him in combat (and having a powerful unit) and keeping him safe at home. I guess giving everyone an Adventurer with, say, a Leader or Monarch promo which caused their defeat if the Adventurer died would do a decent job of replicating those conditions.
How about spicing this a bit up by making the king the leader your are playing
I would love Imuratep's idea of "Leaders" being the "King" units but expanding on it a bit more along the lines of what BeefontheBone.
I remember that Civ3 scenario Beef mentioned (Japanese Conquest iirc), and it was quite fun. My take on it would be that all "King" units begin as just a basic unit (with appropriate graphics, of course), either at 0 Str with 2 move or with stats comparable to a Scout or Warrior (another possibility would be to jack up their defence but leave them with little offence, meaning that a major Warrior rush wouldn't equal instadeath but at the same time they can't go on a Warrior rush of their own). Either way, some kind of stat set-up where they won't be game-defining in the early game. I'd also say a new promotion needs to be added that makes the King unit NOT defend the stack if it's the strongest unit in the stack. It just seems logical that if the game rests on the King unit surviving, that you should have to kill all of its followers on the same tile before getting to it (possibly making it immune to collateral damage as well or putting a cap on how much it can take so that it doesn't die from Fire Ball spamming).
As BeefontheBone said, in that Civ3 scenario you could upgrade your King unit during tech progression and make him a useful unit as well as the object of the game. I could see that being fitting in FFH (albeit there could be some significant balance issues that need to be thought through thoroughly). Keelyn could become "Keelyn the Conjurer" at KotE, Tasunke could become "Tasunke the Warlord" at Stirrups/Horseback Riding, "Falamar the Charismatic" at Sailing and etc/so forth (I could sit here and make up ones for all of them by that'd be overkill)**. It could go further that they have multiple upgrade stages. With the Tasunke example, getting a new boost with each of the horse techs (so that he can compete with his fellow units in strength - after all he is there leader), Keelyn going up with the magic techs, Falamar with the Sailing techs and so on.
**[
I stick all the "____ the ____" names just so it differentiate them from what I assume would be their vanilla names when they're in "basic" form. So it'd go Tasunke, Tasunke the Warlord, etc. That's obviously variable, you could easily change things around like "General Tasunke" or "Captain Falamar" etc, or just leave it at default...I'm just spouting babble now...]
The same "Don't defend the stack unless it's the last unit" rule would still have to apply obviously, but they'd be usable as offensive units and could indeed be great assets to an invasion. The Arcane leaders especially strike me as perfect for having their own unique spells to spice things up (Tebryn for example could bring back Meteors, although looking at Jonas's entry, it seems like he could be more than capable of raining down that kind of fire too).
@Imuratep:
The reason i didnt say to have a unit of the actual leader for Kill the King is that would be 18 new unit graphics that wouldnt even be used in the game other than this. I think just using a great commander unit would be fine, especially since you wouldnt really be playing him a lot, other than maybe moving him away from armies.
I know it's a bit of an unnecessary strain on the art team, but I'd actually love to see in-game renders of the leaders. You could argue that the graphics would be used only in this scenario, but maybe the game could be altered to accomodate them to be usable within normal games. Maybe have a deal like with Hyborem, where if you lose your leader unit, you lose your traits (maybe with a Ritual added where you can get them back, to stop your civ from being completely crippled for the entire game... although losing your leader certainly should be punished). Once again, the main issue I see with this is balance, and also, can the AI use the units intelligently (i.e. don't send it off on its own or throw it into a 40% odds of winning battle)?
Anyway, the Regicide idea really swings by with me

I <3ed that Civ3 scenario and I feel the leaders in this game all have enough flavour to them where they could be added as in game units (most of them have some degree of battle experience, and those that don't could certainly be made to have more "supportive/boosting" roles for their troops).