How about the Leader of the Civ gaining XP ?
That is a common idea in many other games, but you are right it is new to civ. The civ leader is always offscreen, so any ability given to the leader is global. I could envision a trait tree for this leader. It might be increased strength of existing traits, or additional traits.
I was also thinking about "onscreen" leaders. I might experiment with this idea in some other mod, not Fury Road. In vanilla civ, a Great General is "onscreen" and moves around, but his main effect on combat is to give a few units, a few levels of XP. For a particular combat, it doesn't matter whether the leader is there or not.
Suppose leaders had a trait/promotion tree with effects like "+3 happiness in my city", or "+20% combat strength to all units in my stack", or "+25% food production in my city". With a game scale that really takes place in one lifetime, you might have one leader, or maybe as you advance you attract a second or third leader. Each leader would have enough impact that the exact location of the leader is important.
In a multi-generation game, you could also have a family tree of leaders. A leader may grow old and lose promotions. New, young leaders may spring up. It would be possible to have dynasties of leaders, where the child of a leader is not available to lead until age, say 16, but then has some traits related to the parent. This has also been done in other games, like the Total War series, but would be new to civ.