Just hit 60 leveling as prot. I did it back in vanilla, too. I just like the sword and board playstyle.
First thing you have to ask yourself is… Are you in a rush to get to 60? If the answer is yes, don’t level prot. Level arms or fury instead.
Most people I run across are in a huge gd hurry to get to 60 for whatever reason. They don’t enjoy questing out in the open world. They view leveling as an annoying obstacle, and they want to get it overwith asap. And they don’t understand how anyone else could feel differently. Thus they look upon a prot leveler in abject horror and will try their best to fearmonger you into another spec. Don’t listen to them. If you enjoy the sword and board style, and you’re not in a huge hurry to get to 60, then leveling prot is certainly viable.
Tips…
Stack strength/AP, followed by agility, followed by stamina. Avoid pure stamina pieces. You don’t need it because you have a shield equipped, and you’ll render caster mobs useless with your two interrupts (Concussion Blow being the other). You want to maximize the damage you do with your 1-hander for rage gen.
And along those same lines, try to upgrade your 1h weapon as often as possible from quest rewards or dungeon drops, or check AH and invest a few gold into a BoE blue weapon upgrade. Then find an enchanter and put +3 weapon damage on it… it’s cheap… mats are only like 1g. Since you will be using a lot less food/bandages than your arms/fury counterparts, you can put your savings toward this.
If you’re soloing, try to focus on green quests 3-5 levels below you. If you run out of green quests, consider hopping to another zone to do all the green quests there, before coming back in a level or two to do all the formerly yellow ones that are now green. If you have a pocket healer, though, you can disregard this.
Run every dungeon at least once, and gather all the quests for them beforehand. As a warrior, you’re very gear dependant. 5-man quest rewards and drops will get you upgrades. And as a tank, putting a group together is quick and easy.