EDITED
I had a slightly different idea for what you refer to as Provincial rulers. (when everyone is tired of new ideas and just wants to get on with the game, I'll shut up and just go along with the rules)
Anyhow, my idea was that each of the role players, with the exception of the chancellor, could be considered Dukes. As a Duke, the player wouldn't necessarily be represented by any unit on the board. In fact, since he's immortal, he could even be considered a "royal house." The first King would be chosen at random from the starting Dukes. The King could grant a Duke title to a Province or, as the game progresses, multiple provinces. The Duke would then be free to appoint "governors" for those provinces as he sees fit. The Duke would even be free to recruit his own armies and invade neighboring provinces as he sees fit (this would require an out of character communication with the chancellor, which the chancellor would not be able to refuse). Of course, this ability would be limited by the fact that the Duke would be obliged to support the King with taxes and tribute, and it will be extremely difficult to defend your own province while attacking another in this situation unless you had a very large Duchy. This could, however, make for some interesting politics. Duke A asks Duke B for assistance with an offensive mission, in exchange for cash or future assistance for Duke B. So, Duke B sends the Chancellor a message ordering that some of his units be given to Duke A temporarily. The King would have to try to do what's best for the kingdom (and himself) while the Dukes are out trying to increase their own holdings and power.
When a Prince is born, he should be considered the same as a title marker. Since we can't actually simulate princes realistically, the prince could be kind of an honor or reward that the king gives to another player. So, instead of province rulers and princes, we have Dukes who can command multiple provinces and can be "promoted" to prince, and thus, possibly, to king. The King can't give himself a prince, and any new provinces he keeps for himself get passed on to the next king as royal holdings rather than Ducal lands. The royal provinces remain royal unless the current king grants them to a Duke other than himself. So, the current King would have power over both his own duchy and the royal lands. This gives him the power to show some favoritism to his own duchy when it comes to taxes and royal grants for castles, etc.
To make all of this even more interesting, the Dukes could recruit agents, and (again, out of character) force the Chancellor to use Spies, Assasins, and Inquisitors against another players' generals. That way, if I'm a prince second in line to the throne, I can role play at a hostile takeover. If your Prince dies (or is removed from the "heirs" list), you just go back to being a Duke and the prince's bodyguard becomes a regular general in your army. If your King dies, the new King takes over any royal lands, treasuries, and armies, and you retain your Duchy and its armies.
Of course, the Chancellor (whom I won't envy even one little bit) will probably need to be permanent.
I think all of this will promote the inter-player competitions we are looking for as well as a very feudal atmosphere without exceeding the limitations of what we can do with the game.
EDIT: The king would have two methods for obtaining troops from the Dukes. One would be to order up troops as "tribute." These troops would be his permanently, and would be passed on to the next king, along with their maintenence costs. The other method would be more of a "call to arms." These troops would be on loan to the king with the maintence covered by the Duke. The Duke could then recall these troops at any time, with the consequences being an angry king and the political consequences among the other Dukes. I suppose the Duke could even refuse to pay taxes and tributes, although I'm sure the current King would do something extremely nasty if that happened. After all, the king has ultimate power in granting AND revoking provincial titles (unless we agree that a large majority of Dukes can override him).