To be honest, being paladin is going to be a solid choice, especially with the reshuffle.
Regardless of what race you pick, Word of Glory is your best friend.
You'll be getting an attack, Crusade Strike, early on. Spam that attack three times in any fight. Each use gives you a Holy Point. Get 3 holy points and your Word of Glory becomes a free full/major-heal (you can use Word of Glory any time you have a holy point, but it'll be weaker and not as useful when below full).
Once you've used Word of Glory, spam Crusader Strike again until you've got three holy points again. Lather, rinse, repeat and you're functionally invincible so long as your Word of Glory heals more than the enemy can hurt you.
If you're going go into instances via the Looking For Group function, I'd recommend being a Protection spec paladin, because you'll get more bonuses to armor and you can run as a tank, which means you won't have to wait nearly as long as DPS (Damage-Per-Second) or even a healer.
Early tanking is probably going to be pretty easy with Avenger's Shield. Plus, because of it's low cooldown, Avenger's Shield can be added to any spell-rotation when you're facing multiple enemies.
Though, to be honest, I haven't played a Retribution Paladin or a Holy Paladin, so I don't know how easy it is to level one, though I've heard traditionally Holy Paladins are better off running instances once they're available, and Retribution is better for either DPS or PVP. This might not be true, it's just what I've HEARD. I haven't played Retribution or Holydin
If you don't want to wait for Cata's drop, I'd strongly suggest either running a Blood Elf or Draenei Paladin, since I've heard their areas are going to get the smallest changes and leveling in those two zones is fairly easy for Paladins.
I would also strongly suggest asking around for a Friend Account. You get exp bonuses when your characters are within five levels of each other (and are active at the same time, in the same area and both characters are below level 60), you can teleport to each other once an hour. Plus, if your friend is nice enough, they can help you out with the initial costs.
Getting to Level 20 is a BREEZE with a knowledgeable friend.
Oh, and if you're starting out and you can't get a friend account, I'd strongly suggest a few things:
0) I'd strongly suggest picking a low or medium population server that's either "Normal" or "NPVP". PVP servers are cruel and there's no end to assholes who'll grief the hell out of lowbies. With Cataclysm allowing flying over most areas, this will simply get worse. Normal means that members of the other side can't attack you unless you get flagged for PVP (which will happen if you heal an ally that's flagged PVP, attack an NPC or Player flagged for PVP) or you join a battleground.
1) use "/leave Trade" IMMEDIATELY. Otherwise you'll find your chat window bombarded with obnoxious gibberish. If you've ever been on a general IRC, think that, except about thirty times worse.
Also, learn how to swap between chat options.
The default is "/s" or Say, which will simply pop up in the chat windows of anyone within a certain radius. "/y" will yell something across an entire area (i.e. the city), "/w <insert player name>" will let you Whisper a player directly without anyone else hearing (regardless of distance even), "/p" will let you talk to your party, "/g" will let you talk to your guild, "/raid" will let you talk to the raid. "/1" will let you talk on General or whatever happens to be the first channel you're on, "/2" will let you talk on whatever is your second channel, etc.
It's interesting to note that you can't say or yell when you're dead, but you can whisper and talk to your party/guild/raid while dead. You can even talk on channels while dead.
2) LOOT EVERY ENEMY. Run back to town and empty your bags every time your bags are full. Not only will you earn precious money for learning skills, but there's also the chance that an enemy will drop a surprisingly valuable item. Even if you can't use it, it's still worth money. If you want to know how an item compares to what you've got equipped, hold the shift key and place your mouse pointer over the item. (unless you have nothing equipped in that slot, in which case, it'll only show what you're pointing at)
3) Bookmark <a href='http://www.wowhead.com/' target='_blank' rel='nofollow'>WowHead</a> and <a href='http://www.wowwiki.com/' target='_blank' rel='nofollow'>WoWWiki</a>. Some quests aren't clear and others aren't properly marked. You shouldn't be afraid to re-read the quest text.
4) Pick up complimentary professions. Unless you plan to have multiple alts on the same side, it's strongly recommended that you get at least one gathering skill. The extra benefit for a gathering profession is that you get extra XP every time you gather something, so it can be handy to have. You can even have two gathering professions, though you'll want to get VERY large bags as soon as you can.
5) Join a guild. Being low level means you won't be useful for a while, but there are usually a number of leveling guilds around that will support lowbies. They'll sometimes make suggestions on professions, especially if they have need for more items at low levels or if they don't have an excess of people with those professions. Furthermore, guilds will become even more useful for leveling when Cataclysm drops, as they'll give a 10%-20% exp boost.
6) For the most part, avoid buying armor/weapons, especially from the Auction House or NPC vendors. At low levels, it's a waste of money, and at higher levels, you'll usually stumble on better gear just doing quests in the next leveling area.
7) Abuse the Auction House. If you're not doing First Aid or Tailoring, you can usually hawk any cloth you gather for a tidy sum. Search for that type of cloth, find the first few stacks and look over what their average price is per and set yours to sell at about the same. Make sure to add buyout prices at slightly higher and also make sure that you set the auction to last as long as you can. If it doesn't sell, toss it in your bank and try another day or just vendor it.
8) Learn the key bindings. Change them to make them suit you. For example, the number lock is the default "auto-run" key. R is the default "reply to whoever spoke to you via whisper".
9) Look up introductions to macros. They can be handy for creating "OH SHIT" buttons, as well as automated comments, such as "HEY MORONS, FOCUS FIRE ON WHAT I'M ATTACKING!". You can even set up a spell rotation within a macro and free up your task bars. You can only have a maximum of 50 macros though and they're shared across all the characters on a server.
edit: removed the stuff I've already mentioned ;;^_^;;