For the most part you will find gear that Blizzard has determined to be viable for leveling from your quest rewards. Ret Pally gear outnumbers Prot gear at the start of outland. Enchancement Shamen have more gear available than Elemental. For a prime example, check out the level 70 gear that came from the Invasion Event. All the shamen gear was for Enchancement. You can level a pally holy or prot, but Blizzard seems to think that takes longer, so they don't provide much gear for that. Apparently we're supposed to level up ret and then respec at 80. It just doesn't work that way though. Many folks level their priests holy, their warriors as prot, their paladins as prot, their shamen as elemental, their druids as balance, ect...

At the start of Outlands, you may want to just pick up as much plate as you can from Hellfire. A lot of it is going to be for Ret paladins though. Some enhancement shamen mail gear could give you the strength and AP you need to level. You will have a hard time getting some defense gear though, if you are going to try to instance level. It may be easier to level Ret, if you're going to be questing to level up your team instead of instance boosting.

I did not switch my main pally to prot until northrend, where the easily obtained crafted defense cobalt set makes getting instance ready a breeze.