One immortal leader for a civ in 6.000 years in my eyes is a very spoiled concept and it is astonishing that this was never changed in the civ series - especially as a change of leaders for a civ during the game offers a lot of additional convincing possibilities to change the traits for that civ and to add more realism to the game without destroying the flair of the civ series.
In my Civ 3 mod I made use of these possibilities and it works very well. Here are screenshots with the different leader names and graphics in an earlier phase of the developement of the mod:
http://forums.civfanatics.com/showpost.php?p=7596888&postcount=92
And here are some screenshots of a later stage of that mod with streamlined leader names (shown at the example of Egypt), as the full names caused some overlapping problems in the Civ 3 trade texts:
http://forums.civfanatics.com/showpost.php?p=8066459&postcount=186