Yeah that would work fine too.
Perhaps it would be possible to have two different types of "Clan Government". If you assign a Rank 5, then he acts as King as you describe. If you only have Rank 4's then it acts as a kind of "Council" or Republic, where each has equal amounts of power and perhaps a way to "vote" on who gets a new fief.
For instance in the area where you can currently assign fiefs (the one with the pulldown menu) when there is an unassigned fief allow it to select who you want to vote for, from the eligible Rank 4 members, and click "Vote". After enough votes are tallied the fief is assigned to whoever gets the most votes (similar to native). Also possibly have it so that the more fiefs you already own the less voting power you have. So:
No fiefs - 4 votes
1 Fief - 3 votes
2 Fiefs - 2 Votes
Ect.
I dunno, just some random thoughts.
Instead of set ranks or anything, you could just impose a general fealty system, whereby players declare their fealty to someone. That someone could then declare their fealty to someone else. This would be a relatively flexible system of lieges and vassals. You have power to control the rosters of any of your vassals, or their vassals, and so on, but your liege or your liege's liege, and so on, could control your roster.
Each faction can make up their personal own titles or hierarchies; whether the classic feudal pyramid, an oligarchy of lords, or even every member sworn to one king. Personally, I would like to see penalties such that it becomes impractical for any one player to have a large number of vassals, such that there is greater distribution of vassals, and not just everyone swearing fealty to the clan leader. (Eg. A tax based on the number of vassals). I feel this would be more in keeping with the spirit of feudalism, as well as distribute power more so that relative importance is not concentrated on a few people, but spread around.
Of course, one of the major obstacles to feudalism isn't just the infrastructure, but is also a matter of changing the mindset of players. This can be done to some extent by changing infrastructure, but some aspects can always be worked around. You have to have players feel as if they really own fiefs, and it should be a grievous insult if a faction leader asks a lord to give a fief to someone else. Also, we would probably need to inspire greater loyalty just to one's individual liege lord than to the designated faction leader. For example, if a lord goes rogue from a faction, it should be more common for said lord's vassals and their vassals to support their rebellion rather than rein them in. I'm not sure how you would encourage this kind of behavior by changing the system.