Well you warriors had plenty of Paladins back in TBC, its your own fault for being so mean to prot/ret paladins over the years that forced Blizzard to make prot/ret such an attractive spec to play instead of holy!
If you place tank Vezax in 25 man and decide to try a UA build, you will absolutely have to use a 2 min / 2 min variation. You'll also probably want to have your interrupters kick out searing flames earlier in the cast rather than later. Long cast times + slow swings = rage.
I really think its a good idea tho, and I was thinking of doing something similar for Vezax 25 hard mode. When we did get the 10 man cheeve tho, I did use just a standard deep prot 2/2 build.
Oh yea, you'll want to open up with Last Stand as your first trick instead of Shieldwall, that way if your DPS is on track when the Saronite guy comes out you'll have your Shield Wall for that Surge.
Rethinking this a bit with enough disc. priest / paladins, you could probably get away with not having so much of a trickbuild. Maybe just a shieldwall glyph.
Take some of our paladins. It seems that apart from me and a warrior tank, all the other tanks are paladins. We have a couple of rets too, and a couple of holydins (though one did recently switch to his rogue).