What about assassinations? Make them level based to go along with the promotions ideas.
Newbie spy could assassinate workers, settlers or military units, using poisons, sniper tactics, etc. so he/she can't be retaliated against unless caught.
Next promotion would allow assassinating a citiy's population, reducing the pop. by 1.
3rd promotion allows assassinating great people and super specialists.
4th and final promotion, with a huge cost to attempt, can assassinate the leader of the civ. If successful, another leader for that civ takes over. IE. kill Washington and Roosevelt takes over. After all, if the leader is assassinated it'd be a major disruption to the civ targeted.
Perhaps add a few aditional civ leaders for each civ, that only appear after an assassination. You can't ever get them as a starting leader. Each leader will have different traits of course. So you might Start with an Agressive/Expansive and end with a Spiritual/Philosophical leader. Imagine how that would effect some multiplayer games.