I should point out, as of now, the Horde has no reason to want to de-throne Garrosh.
At least, no more reason than the Alliance has to de-throne Varian. Sure, they're both warmongers. Sure, they're both brash.
However, this expansion has been one of character development for Garrosh. He's become a competent leader, and done /well/ by his people. While the people of Westfall starve, Garrosh has put a roof over all of his people's heads, and food on their plates.
He's also taken a stronger stance against demons within the Horde (granted, most Horde races have a strong reason to hate the Legion these days, even Forsaken), likely a good thing. He also does not tolerate war criminals, in /any/ way. Garrosh doesn't want to destroy, or even scar the world - even Stonetalon was not the will of the Warchief.
So, in order for the /Horde/ to turn against Garrosh, there's got to be some new development. Either they'll be lazy, and he'll go ~inexplicably crazy~, or they'll do something with one of the things noted in the press release:
'Unwary mortals can also become possessed by negative Sha energy, becoming embodiments of pure anger or fear.'
That'd be my best bet.
As for who takes up the reins of Warchief, I'd imagine it'll be someone Orcish. Thrall, maybe. Metzen did say he'd be rejoining the Horde in one way or another. Saurfang, perhaps, as he was the -first- to tell Garrosh that if he stepped out of line, he was dead. Vol'jin and Baine are also possibilities. There's also the possibility of a new character, though I doubt people are much interested in having a Warchief we barely know. Eitrigg's probably too vested in the Crusade.
Also, I'm just glad Sylvanas isn't getting the 'omg she's evil, kill her' treatment after /all the Forsaken quests/ explain exactly why she does what she does, and how she's not evil.
Edited by Vanyris on 3/19/2012 1:37 PM PDT