I wouldn't even try prot leveling until 30 when you get Blessing of Sanctuary. Even 30 is a bit early as you'll also need Reckoning and Holy Shield. I'd go for something like this:

http://www.wowhead.com/talent#sZV0xA0uxho

Until then, Ret will be the fastest. Just my opinion.

After my first Paladin (Prot) I made another, and found I could tank at least BRD successfully as Retribution, as long as I equipped a shield.

Honestly, I wouldn't spec Protection until 75. It was like torture without SotR.

Dur... I mean SoR - Shield of Righteousness.

I leveled a prot paladin to 60 entirely via the dungeon finder and I can say that the only seriously painful stretch is tanking Wailing Caverns before level 20 when you get Consecrate. After that you may start running into issues with mana until you get Sanc so be sure to carry lots of drinks, but I successfully tanked every single vanilla dungeon while leveling.

I leveled prot as well and I agree with the above comment that it's only hard until you get consecrate. I will say that dungeons DO go faster if you are ret and are somewhat skilled, AS LONG AS YOU HAVE TANKY GEAR. Seriously. If you want to queue as a tank, ever, make sure you're saving the tankiest gear you can right from the get-go, and always have the best shield you can find and afford because it makes a difference. Sure, you *can* tank Deadmines with a 2-hander, but it's going to go slower and I will be silently hating your guts.

Also, I would not stay ret past the point where you would pick up Avenger's Shield (I don't remember what level off the top of my head anymore, since I don't really pay attention that closely to when I get stuff, just that I got them). I have run with amazing ret Pallies in BRD (wearing tank gear), so it's doable up to that level or so. But please, unless you're running with good healers or are exceptionally skilled, err on the side of caution and level prot- the AOE grinding between dungeons (yes even tanks have a *little* wait time) can be awesome.

I lvl prot from 10 to 70, when 70 was cap. Found it so easy it was almost laughable....Solo 5 man group quests (easy as piss), also very good for impatient people as intant pops for LFD these days.

Lower level tanks who dont have sanc plz just judge wisdom/ seal wisdom when in 5 mans...... less dps, but at that level who cares? less down time everyone can agree with.

Also before wrath hit i spec'd Ret, and was able to trank/heal dungeons (with odds and ends tanking/healing sets picked up a long the way) upto Violet hold withought even breaking a sweat, and then upto Heroics (but not heroics) if i was really on the ball while in RET SPEC.

To be blunt, untill heroics as long as you have (not even good) a decent off set , and perhaps just a touch skill , a pally should be able to tank heal or dps in ret spec

The way I leveled my pally was spec into Ret for Seal of Command (acts like a cleave) pick up the glyph for it (goodbye mana problems) then spend the rest of your points in the prot tree. sure you get the important prot talents 10 levels later then pallys who didn't spec into ret, but you will have a much easier time with threat. that is just my experience though