Non-Paladins as Death Knights
How can non-Paladins become Death Knights, you ask? It's actually rather easy. In fact, the first Death Knights came into being before the Scourge or Paladins even existed. These Death Knights, created by Gul'dan, were made from the bodies of slain Knights (which could not use holy magic at all) imbued with the spirit of Orc Warlocks and necromantic energies from slain necrolytes. Since the Scourge were once simply an arm of the Burning Legion, it stands to reason they could do similar - if not planting new spirits in the bodies of fallen knights, at least giving mundane warriors the power to wield dark magic. After all, Death Coil and Death and Decay have been Death Knight staples for both types of Death Knights thus far, and will apparently once again be part of the WoW Death Knight's Arsenal, which implies some kinship.
Similarly, we already know of at least one Knight who was not a fallen Human Paladin. Thane Korth'azz of the Four Horsemen is a Dwarf. This at least proves that non-Humans can be converted to Death Knights. You can also probably reasonably cast doubt on whether Korth'azz was originally a Paladin, as it is generally strongly implied that Dwarves really didn't take up the mantle of Paladin in large numbers until after the events of WC3. In addition, Korth'azz is called a Thane, which is generally a title given to the Clan leaders of the Dwarves, or to Mountain Kings, meaning that Korth'azz himself may never have been a Paladin at all.
How the Lich King can create new Death Knights
And how, you ask, can races such as Gnomes and Draenei, who did not have a presence in Northrend during the third war, have found the time to be seduced by the Lich King and become Death Knights? There's many good reasons for this.
Firstly, remember that the Lich King's grasp is long. He is able to whisper dark things into the heart of people even from many miles away. It was his only way of communicating when he was encased in a block of ice, and how he first established the Cult of the Damned. As he whispered dark things into the heart of Kel'thuzad and many of the other members of the Cult to seduce them to his side, so he could with others. He can see the darkness in your heart and exploit it.
Secondly, we also know he sends out emissaries who, while under his control, are capable of speech and sentience. They seduced the Razorfen Quillboar, and they could seduce various members of the races, members who are experiencing negative emotions, who lust for power or vengeance, or have some other weakness to exploit.
Thirdly, we know that he twists good intentions. The first Paladins to become Scourge Death Knights headed north to stop the plague, not to become its agents. Arthas himself believed he was fighting the Scourge til the moment he grasped the hilt of Frostmourne.
Finally, by the time we get to Northrend, it should be noted that the NPCs will probably be there before us. Just like in the Burning Crusade, when we came through the Dark Portal to find the Cenarion Expedition and the Falcon Watch well ensconced, we may very well find that expeditions have been sent to the north for longer than we might have expected, be it advanced scouts for the Forsaken, Dwarven Explorers, or search parties for the Scarlet Expedition that was lost in Northrend so long ago. It's very probable that some members of these advanced forces, constantly under siege by the undead, might have found themselves ground down and agreed to join the Lich King for a respite.
As you can see then, there is already some argument for non-Paladin Death Knights, as well as some arguments for how the Lich King could have created new Death Knights since the events of Warcraft 3. So now that we've established some basic lore and reasoning for why the Lich King has been able to recruit Death Knights of all races, let's look at some of the major ways in which members of each race could fall into despair at the hands of the Lich King. Hopefully the following list will both serve to explain why each race can justifiably be Death Knights, and give my fellow Roleplayers a few ideas as to how they might roleplay or develop a backstory for their Death Knights.
Human: The Lich King himself is part human, containing the body and soul of Arthas. Also, many other humans agreed to serve the Lich King willingly, including the original Scourge Death Knights and many Liches. Paladins shunned by superstitious people, they went north to fight the Lich King, but battered by temptation and fatigue, made a deal to serve him instead. It was a human, Medivh, who opened the Dark Portal. The possibility of corruption certainly exists in this race.
Gnome: Despite their inquisitive and cheerful natures, Gnomes have a dark side as well, a perchant for wanton destruction that causes them to undertake dangerous experiments or even tinker with the dark arts of the Warlock. Some overly adventurous Gnome may have conducted experiments that opened his mind to the Lich King's corruption. Many of them, too, may have been driven to anger or depression by the betrayal and the destruction of their city, and may have turned to the arts of the Death Knight in order to reclaim their home and their birth-right as true and noble nation rather than the near-homeless house guests of the Dwarves.
Dwarf: The Dwarves are known by many to be stout-hearted and noble, but they have a greedy and racist side as well, going to great lengths to dig for gold and gems, even if it means massacring the natives to make it happen. It is more than possible that more than one Dwarf of the Explorer's League dug too deep and became too greedy, and when offered power by the Lich King, chose to take it. Some of the Dwarves from Muradin Bronzebeard's expedition may have grasped on to the Power of the Lich King, believing it to me their only choice after they became stranded in the frozen north. We've already seen a Dwarven Death Knight in the Four Horsemen, as mentioned above. It seems possible that he was a member of Muradin's expedition.
Draenei: While most Draenei are devout and noble worshipers of the Light, they too can have a dark side. Unless we forget, they came from the same race as the Eredar, and certainly the corrupt thoughts that marked the Eredar can still seize them. Kaylaan the Lost, a young Paladin corrupted by the Eredar when he lost faith, is perhaps the perfect example of how a Draenei could be corrupted by the Lich King. The evil, soul-stealing Auchenai Death Cult, which is made up almost exclusively of Draenei and indulges in necromancy, is an example of a nihilistic spirit that has gripped many Draenei and could inspire some of them to join the Lich King. Also, Many Draenei may just be tired of running from the Legion, and may find that they prefer to make their "last stand" with the Scourge, to stop running and give in.
Night Elf: The Night Elves have lived as a solitary people for some time now, and though many have assimilated into the wider world once again, serving it as members of the Cenarion Circle or the Alliance, many have become bitter, angry, or even arrogant. Perhaps anger at the invasion of the Horde into their territory might drive some to be seduced by the Lich King. Many, as well, may be looking for some way to regain their lost Immortality. If Elune and the Dragons have forsaken them, they shall take the Lich King's offer, and he will grant them immortality and power that the Dragons refused to when they refused to bless Teldrassil. It's also worth noting that many Night Elves have fallen away in large numbers before, and made pacts with dark powers that nearly destroyed Azeroth and twisted them beyond recognition. Thus, much as the Satyr and the Naga are fallen offshoots of the Night Elves, so too could some Night Elves fall and become Death Knights.
Orc: The Lich King himself is part Orc. He was once known as Ner'zhul, and he ordered the massacre of the Draenei, an action worthy of a Death Knight if ever I heard one. Both he and Gul'dan, to various degrees, orchestrated the opening of the Dark Portal and the first and second wars against humanity in the name of power. In addition, some Liches were once Orcish. The same lust for power that drove them, and the bloodlust that drove Grom Hellscream and Kargath Bladefist to drink the blood of the pit lords time and time again, could easily drive some Orcs to make a pact with the Lich King. Many of them, such as the Warlocks who turned into the original Death Knights of the Burning Legion, might turn to the darkness again.
In addition, the Orcs of today are often bloodthirsty and arrogant, claiming a manifest destiny to take over Kalimdor, even if it means wiping out any indigenous species that defies them. Certainly, that sense of entitlement would be perfect for the Lich King to exploit.
Troll: Certainly, the Darkspear tribe has given up some of the more savage parts of their heritage such as cannibalism, but don't assume they've completely reformed. There are Darkspear witch doctors in many parts of Azeroth who are not above a little bit of voodoo to kill the alliance or capture the spirts their totem animals. In addition, you have Zalazane, the dark witch doctor who turned against his people and drove them from the Echo Isles. That same darkness must rest in the heart of other Trolls and make them easy to turn. Finally, some trolls, especially the tribe of the Revantusk of the Hinterlands, who seemed to nearly worship him as a god, might feel some bitterness over the fact that the Horde joined the fight against Zul'jin, who is considered a hero by many Troll tribes.
Tauren: These gentle giants and their culture might belie any thought of evil at first glance, but there's more than a few signs of darkness even in Mulgore. The Grimtotems, especially, are suspect. Magatha Grimtotem, who may have killed her husband to become leader of the clan, also shows an unhealthy interest in the art of necromancy, and there's evidence in Thousand Needles that the Grimtotem are allied with the Razorback Quillboar, and through them with the Scourge. There might be Grimtotem Death Knights already, who gave themselves to the Lich King at the behest of Magatha.
Beyond the Grimtotems, other clans can feel darkness in their hearts as well. Many clans have been in constant struggle with the Quillboar and the Centaurs, and the Dwarves have driven at least one clan off of their lands and are pushing into Mulgore. It's certainly possible that some may have taken the offer of the Lich King in order to exact vengeance for their lost land.
Undead: The Forsaken are, all in all, a twisted race. Saved from mindlessness, they have nevertheless lost much of their emotion. Rot and decay are now beauty to them, and their world is black and white. Many of them feel little but bitterness, be it against the alliance, the scourge, or against the unjust world that condemned them to undeath. Such negative emotions are perfect for the Lich King to prey on. Arthas' hatred of the Scourge did not prevent him from becoming the first Death Knight, so he will certainly know how to twist the hatred of the Forsaken to his own ends.
Other pre-existing Human Death Knights from the third war may simply decide to go to Lordaeron instead of Stormwind when they break free, especially if they have deteriorated so much as to look more Forsaken than Human.
Blood Elf: While Liadrin has finally seen the light, there is much anger and thirst for vengeance among the Elves. They've shown the tendency to become wreckless in search of power - Kael'thas, their prince, was driven to his death by it, but all Blood Elves, even those who have stayed with the Horde, have partaken in once-forbidden Demonic magics. Many Elves who felt abandoned by the Light may still feel that way, and may decide that the darkness will be a better master. Some, perhaps, will be eager to exact vengeance against the Night Elves and Dwarves for invading their land and will be willing to accept the Lich King's help to do it. Still others may be mourning over the death of Kael'thas, who was once almost worshiped by his people as the Sun King who would lead them to glory. Certainly, There are many ways for the Lich King to lead a Blood Elf astray.
For those of you who still aren't convinced, you can hold on to the hope that we're still in the very early testing stage of WoTLK, and things may change, and that Gnome Death Knights may go the way of Dwarf Mages. Me, I'm pulling for Death Knights to remain members of all races. It's both a great way to add a little bit of variety and customization for individual characters that sometimes seems missing in the game, and provides a chance to send the story of WoW off into new and interesting directions, as each race has to deal with their own demons and see them come home to roost in the form of the Death Knights, and whatever sins and sorrows caused them to take up a Runeblade.