On a planet not too different from Earth, in a land quite similar technologically to ancient Rome, there is a dynasty of absolute monarchs that have remained in power for centuries. They enjoyed periods of prosperity, peace, and popularity, but within the past fifty years or so, discontent has arisen as the public believes that the monarchs have been abusing their power and doing only what they want to do.
In desperation, King Shenaeth the Magnificent goes to the temple of his ancestors, where he prays for help. To his surprise, a potion appears before him, along with the murmur of words through the air, telling him that if he drinks the potion, he and his descendants will be immortal (they have the same type of immortality as the folks described in How would a war between immortals be fought?; they can regenerate lost body parts as well as avoid the typical non-violent causes of death.).
Shenaeth drinks the potion, and announces to the people the next day what has happened. They now cannot kill him! He reminds them that he has total control over the military, too - did I mention that the soldiers already worship him as a god, and devote their lives to him? - and sends an implicit message: He is supreme and immortal.
Over time, Shenaeth's kin multiply. He remains at the head of the country for several centuries, during which he builds up an army (of immortals) and conquers much of the globe. Eventually, any virtues he may once have had disappear, and he begins exploiting the population. Discontent rises, and several groups of underground fighters (with overwhelming public support) decide to plan a revolution to overthrow the government.
How can these fighters overthrow the government of immortals? They don't need to kill Shenaeth; they simply need to remove him and his family (and extended family) from legal, military and political control over all the lands.
Additional specifics:
- The standing army is roughly 7.5 million troops, with all but 10,000 being mortal. However, almost all of the top officers (~95%) are immortal, and have great sway over their troops.
- The population under Shenaeth's control is about 200 million people. Rebel groups consist of about 5 million troops (in a standing army), while estimates put folks "in reserve" (those who would fight for the rebels if need be) at around 25 million. The rebel forces are (extremely) loosely organized, and there is no central command structure.
- The overthrow should last for at least 25 years - enough for a government to get control over the region and start implementing pro-democracy policies.
I've considered the idea that power rests in the hands of the people, and that the people could simply choose to recognize a new (rebel-led) government as legitimate, but they would still eventually be overpowered by Shenaeth's military.