The Four Horsemen were a group of elite Death Knights in Naxxramas. Zeliek, Blaumeux, and Korth'azz were in both versions of the raid, while their leader in the original Naxxramas was Alexandros Mograine (the original Ashbringer, who wielded and could drop the Corrupted Ashbringer,) but in the lead-up to the story of Wrath of the Lich King, Alexandros' son Darion raided the dread citadel and took the sword, plunging it into his own chest in a sacrifice to free his father's spirit. Darion of course then rose as a Death Knight of the Scourge, but thanks to the redemptive power of the blade and the Holy power within Light's Hope Chapel, Darion and the rest of the Ebon Blade (including you, if you play a Death Knight) were broken free of the Lich King's dominance.
With Alexandros gone, Baron Rivendare - a nobleman from Stratholme who joined the Scourge willingly and used to be the boss of the undead half of the Stratholme dungeon - took his place.
Naxxramas was raided once again, and it looks like the Four Horsemen are now canonically taken care of.
But the invasion of the Burning Legion is making for some strange bedfellows. Spoilers to follow:
First off, we know that the Ebon Blade is going to form an alliance with the new Lich King - combining their forces to help destroy the Legion. While "evil" may be a relative term in this case, Bolvar is definitely not the noble paladin he once was, though you could certainly argue that he's working for the greater good. The Ebon Blade recognizes the Death Knight player character as Deathlord, who serves as the liaison between the Blade and the Scourge.
There have been some quests revealed that imply that the Ebon Blade wants to recreate the Four Horsemen to fight the Legion. But it will have new membership.
The new Beta patch contains some very interesting voice files. It appears that Darion manages to contact the spirit of Arthas, who seems convinced that the "darkness" will take everyone eventually, though whether he's referring to the Void or the Scourge is unclear. He cautions Darion not to trust the Lich King - which is pretty crazy given that Arthas was the longest-serving Lich King. It really implies that the Lich King as an entity exists separately to the people who occupy the role. Ner'zhul, Arthas, and now Bolvar are really serving this god-like being.
Still, the agreement to raise four new horsemen goes forward. And we've got a roster:
High Inquisitor Whitemane, one of the top leaders of the Scarlet Crusade, going to be one of them. Darion hopes that death cleanses the madness that consumed her in life. Fingers crossed!
Next we have General Nazgrim - obviously, this guy was a noble Orc and fierce warrior. Though we killed him in Orgrimmar, we did so simply because his code would not allow him to betray his Warchief, even if that Warchief was a mad fascistic prick who had started meddling in the magic of the Old Gods.
Thoras Trollbane is the third, one of the founding members of the Alliance of Lordaeron. With Stromgarde in ruins, Trollbane's legacy is already in tatters, so serving in the Four Horsemen might be a way to achieve something.
Finally, this one's really tough: Tirion Fordring. In the battle against the Legion at the Broken Shore, Tirion is captured by demons. And while Paladins are sent to rescue the Highlord, he ultimately succumbs to his wounds, passing on the Ashbringer to players. But given how important a hero he is, the Ebon Blade cannot think of a better leader for the Four Horsemen, and so they'll mount a raid into Light's Hope Chapel to steal his body and raise him.
Given that I play a Paladin as my main and a Death Knight as my primary alt, this is totally insane, and I'm kind of torn. On one hand, Death Knight Tirion sounds totally badass. On the other hand, damn if that guy didn't deserve a good rest in death. In fact, in the Retribution artifact quest, you literally see his soul ascend to the heavens. Do the Death Knights grab it and stuff it back into his body? Not cool, guys!
Anyway, what role the Four Horsemen play once assembled remains to be seen, but it's pretty cool to see a bunch of dead lore figures added to the mix (though it'd have been cool if there were more non-humans in the mix.)