Man, I came up with two really good specs for leveling but having a hard time deciding on which way to go.
Prot/Holy Hybrid
https://tbc.wowhead.com/talent-calc/paladin/2550300052013050135-05305133000001
This would give me the best chance to dungeon and also really strong at aoe grinding. Should be very hard to kill in general and very flexible. This spec will hold agro far better as well. The big con is single target DPS is going to be slower and less efficient. I would take Prot to 30 then start down the Holy tree.
Stat focus INT, STA Not sure if Spirt before Str but probably.
Prot/ Ret
https://tbc.wowhead.com/talent-calc/embed/paladin/-0530513300000152521051-052300513
Take Prot until 34 or 5/5 reckoning and go full ret and bounce back to Prot.
This should be much tankier with higher hp. Single target kill speed should be good and fairly efficient. You are only going to run as a tank for groups so a little less flexible. It should also be easier to gear. Also, the 15% movement speed is really good for leveling in general.
Stat Focus: Sta, Str, Int, Spirt