I'm sure this has been done a million times over. Still it's a fun game to play. Here's what I would propose in a hypothetical expansion (or staged through several). Not all original ideas, btw, a mash up of good ideas I've read/heard about, and ones I thought up myself too.
Basically my idea is of the 'create a third faction' school of thought. However I wouldn't just release an expansion with a whole new faction in it for two reasons. First of all it would be monumentally larger than your regular expansion, second of all it would take the romance out of what could be a cool intro.
Instead I would propose first hinting towards it in quests, start building more or less playable towns, that are hostile to both Horde and Alliance. Have plotlines concerning rising threats and apparent organisation of murlocs, naga, twilight hammer, and nefarious clues of fel/old god affilitations.
The first real step into creating a third faction would be to make a 'prestige faction', like the death knight- it isn't available to everyone or newly created characters. Instead, I'd put in a questline that results in a faction/race change if followed through. It would only be accessible to Blood Elves and Draenei. Basically it would concern Kiljaeden, temptation, and fall from grace. For the Blood Elves, they would succumb to their craving for fel magic- emerging as felblood elves hostile to Horde and Alliance. For the Draenei, they would have their purity corrupted and emerge as Eredar- allied to the Felblood Elves and subjects of Kil'jaeden.
The beauty of this is that it would require relatively little legwork on the part of Blizzard. Eredar and felblood elves could use largely the same rigging and mesh of their related extant playable races- the only real difference being texturing. The faction language would be Eredun for the Eredar, and Sindassi for the Felblood elves (which was what Thalassian was originally going to be called, referencing Sindarin from LotR- in this case being fel influenced Thalassian). I've toyed with the idea of an anti-paladin class, like blackguard or doomguard or something, for Draenei and Belf paladins who undergo this transfer- but you could just as easy make them DKs and explain that they needn't be considered undead. Another nice touch would be to make it difficult to do- like you would have to gain Twilight hammer reputation somehow, probably by doing evil things.
Alright. Once that is done, and the hype has run it's course you open up the availability for other races to join this new proto-faction. Questlines and lore indicate that the Satyrs, though originally to be another descendent of the Kaldorei, have infact been kidnapping people of lots of different races and using fel magic to turn them into Satyrs. That would basically be how all of the other races could become demons. Medium sized races become Satyrs (who would need a model update, ofcourse), small ones would become imps. Just like with the Draenei and Belves, it would be a highish level prestige quest that initiated the transfer. The home city would be in Outland somewhere. Thus you'd then have a decent sizish semi-faction of high level Alliance and Horde defectors to Kil'jaeden. However, it would still be limited, and remote, based in Outland. At this point it would function as a novel PvP option, really.
Thats when the proper expansion comes. The Great Sea. The Naga, An apocalyptic tribe of murlocs who worship the old gods, and Twilight Hammer Ogres become playable. These three, as hinted in earlier questlines, have formed an alliance of sorts, each of course with their own goals. Cho'gall and his twilight Hammer Ogres of course want the apocalypse. The Murlocs serve the mad old gods and also relish in the destruction of Azeroth. The Naga have age old fel affiliations and probably serve Kiljaeden more directly. These three pull off a monstrous rite of summoning which causes the plane of Outland to crash into Azeroth- bleeding the two locations together, and creating a cointerminous zone between the two worlds in the southern region of the Great sea. Essentially you'd then have Outland opposite Northrend on the Azeroth map- rather than on a map of it's own- as a souther continent of sorts. However there would ofcourse still be an otherworldy transistion and affect to it. Outland is not *in* Azeroth, but rather conjoined with it. Crossing that threshold would be a bit like approaching one of those Oblivion gates in Oblivion.
At this point, you would have a fully fledged 3rd faction. The naga, Ogres, and Murlocs would be obvious choices. Other cantidates for this faction would be the Qiraji and the faceless ones. The Alliance and the Horde would of course be totally opposed to it- however under Garrosh, diplomacy between the two has degenerated to the point that they cannot unite to fight this common threat. So the Horde and the Alliance still mercilessly fight it out, whilst at the same time Both factions fight against this diabolical new faction.
Some details about the faction. The leader would be Kiljaeden, analogous to Garrosh and Varian. Eredun would be the master language of the faction. Lady Vashj would leade the naga, Cho'Gall would lead the Ogres, Lilki of the White Shark tribe would lead the Murlocs, Prince Xavalis would lead the Satyr, with Gazakroth representing the Imps, The Eredar would be led by Kiljaeden himself- finally the Fel Elves would be led by Rommath (who was the first to undergo this transition- because he looks shady and was close with Kael'thas).
Most of these races have languages already (Nerglish, Nazja, Giant, etc). If the Qiraj were joining they would be represented by the twin emperors.
Playing this faction would be like playing Undead in Warcraft III. Not remotely heroic. You wouldn't be foced to play dark anti heroes trying to do the right thing. You could just be a villain, unashamedly so. I think it would be fun. Other details and updates would include more comprehensive water mounts- for the Naga kingdom. I can see Naga possibly as druids as well, with kickass animal forms- however Cenarion circle would never accept them. I might recommend Trolls Worgen and Naga start their own druidic asscociation which focuses on the darker more predatory and chaotic side of nature- rather than the Tauren and Darnassian orderly shepherd/gardener approach. That might lead on to a subsequent expansion dealing with the emerald dream, who knows.
Ah yes, Ogres. One head or two? This is a tricky one. Obviously the easy thing to do would be to say one head only. I see this as a cop-out and missed opportunity though. Do it as lore seems to imply- if you are a mage (and possibly warlock) you get two heads. I'm not sure how that would work with necklaces and hats- but a fair solution could be devised I'm sure. Maybe let them have two hats, but only benefit from one at a time- being able to switch at leisure as a racial bonus *shrug*. Naga not having legs is a bit of a problem- for using mounts and flightmasters. I don't see it as insurmountable. Female naga having 4 hands is no big deal, if you ask me. Look in world- despite having 4 arms they normally only wield one weapon. Just do it like that and animate it cool. Braces and gloves get applied to all 4. Maybe give them a balanced racial bonus related to it.
What do you guys think?
Oh tl;dr
Third fel/apocalypse Faction
Blood Elves->Fel Elves
Draenei->Eredar
All other races->Satyr/Imps
Naga
Murlocs
Ogres
Homeland is Outland, which is summoned to south of great sea to join the world map proper. Faction starts off as a limited protofaction accessible only through a high level questline. Three way opposition between three major factions.