To make a Death Knight character, you have to have a character of ANY other class, who is at least level 55, on your account. The existing level 55 character doesn't have to be on the same server as the one you're making the Death Knight on. If you deleted your level 65ish character before you quit, and don't have a level 55+ character anymore, then you won't be able to make a Death Knight.
For the most part, there is no One True Path to leveling. All the races are pretty balanced against each other. While some have advantages in PvP, and you can earn XP in battlegrounds now, that's a fairly limited avenue for advancement. One race stands out, however; Humans get a +10% to reputation gains as a racial innate ability, so in that respect, they can advance a bit faster than most.
That said, there are some general rules to leveling quickly:
First, avoid classes that are dependent on others. Melee damage-dealing classes that lack self-healing abilities (such as rogues and warriors) often have more downtime than others. They truly shine in groups, with healer support, but alone, they spend more time resting.
Second, some classes are more versatile. Paladins, Death Knights, Druids, Hunters and Warlocks are all good at being very self-sufficient. Death Knights, Druids and Paladins have
strong combat abilities, good defenses, and can self-heal pretty efficiently. Warlocks and Hunters have pets that fight for them (tank) while the player engages in ranged combat; After (or even during) the fight, the player can heal their pet. This keeps downtime low.
Third, questing is the fastest way to level. When questing, you're getting xp for fighting monsters, and bonus xp for meeting objectives while doing so, plus possibly other rewards (money, gear, etc) on top of monster drops. Of all the ways to level, dungeons are the second slowest xp gain rate, because the monsters are the same level as ones outside the dungeon elsewhere, but are several times (or more) stronger. The only way of leveling that is slower than dungeon groups, is a low level character being run through the dungeon by a high level.
Fourth, if you pick one of the five classes I listed above, some specs are better than others for PvE leveling. Demonology for Warlock, Retribution for Paladin, Feral or Balance for Druid, Blood or Unholy (gives a pet) for Death Knights, Beastmaster for Hunters (Marksman works too, but is more of a PvP spec). With the new dual-spec ability (costs 1000 gold, available at level 40, lets you switch between two talent specs, glyph sets and gear specs without paying respec costs each time), you can even mix and match; For example, my main is a paladin, and dual specs Protection and Retribution specs, so I can go DPS spec (Retribution) for quick kills, or Protection and be a tank in a raid group or heroic dungeon.
Fifth and last, Death Knights start at level 55, and their newbie area not only gives them nice gear, it also leaves them in the level 58-60 range when they finally finish it. So if you want to get to level 80 fast, having a character who starts at 55-60 is quite the shortcut. Just be aware, Frost spec is somewhat overrated; A Frost Death Knight can tank, kinda like an Arms Warrior can tank...possible in theory, but unless you are AMAZING at it, most healers will be calling you Manasponge behind your back.