I know that captains respawn simply by passing time, or "allowing" a random Uruk to kill you will get them promoted to Captain.
But how do Captains get promoted to Warchief? I spend a while using the "Pass Time" function and while lots of captains were generated, none ever got promoted to Warchief. 4 of my warchiefs are dead so there is room for a captain to just step up.
Captains can get promoted to Warchief when doing "Duel" events.
Here is what a Duel icon looks like and the description of one.
Although the best way to get a new warchief is to accomplish Betrayal missions.
Even at the top ranks, there is always struggle for power. A Warchief’s bodyguard might betray him and damage or outright kill him. If the initial assassination attempt is unsuccessful, the betrayer will have to fight the Warchief and all his other men which would certainly mean his death.
If players choose to step in at this point and kill the Warchief, the betrayer immediately becomes the new Warchief and gains a power level. This is useful for drawing out a Warchief with the plan on killing him especially if one of his bodyguards is already dominated by the players.
(Credits for Betrayal mission)
The new warchief will be one of the captains serving the one that just died.
Another simple and fast way (which is also non-lethal) to promote Uruks rapidly is to go to a Forge tower and Advance Time over and over again. Eventually, some random captain will take the place of the deceased Warchief, and voila, you can now brand him, or kill him if you want an epic rune (but you can also use advance time further to get other members of the Nemesis system over power level 10 to get an epic rune, regardless of rank.)
It can also be used to level up Uruk captains over power level 25 and get the achievement associated with that action. Although, by that point, he probably would have virtually no weaknesses so you would need to interrogate a normal Uruk instead of a Worm or a Captain in order to have an easier time beating him.
I advanced time over and over and over again and eventually, I had a new set of Warchiefs in Udün and power level 14-19 captains serving power level 9 warchiefs. Additionally, it's interesting to see the dynamics that take place each time when you do advance time, for example, a level 20 captain facing down a Graug and succeeding, a level 17 and a level 16 dueling for supremacy, and a level 22 having a feast for his followers, only to be ambushed by the pathetic level 6 newcomer. It's really fun to let the Nemesis system take its course. All Talion has to do is stay in stealth and let the game do its own thing.
Additionally, there was one Uruk that killed me maybe 16 times, and was guarding a level 6 warchief. He was level 23. He lost a beast hunt with a Graug and my "Nemesis" is no more. Branding that warchief was the easiest thing ever, since he had no others, and I used wraith flash to scare off the other normal Uruk.
