ZA is entirely possible without a paladin tank. My guild started ZA without one, and we still regularly have two warrior tanks. There are three particular places (that I've done at least) where a paladin tank is advantageous, but not necessary. These places are the gauntlet leading to Akil'zon, the lynx packs on the way to Halazzi and the dragonhawk adds in the Jan'alai fight. Keep in mind I haven't done Hex Lord or Zul'jin yet. We've only tried Jan'alai a couple of times and our raid leader did respec Prot (he's normally Holy) that week, but I can share how we deal with the others.
Akil'zon's gauntlet: MT tanks the two elites (Wind Walkers/Protectors), OT tanks the warriors. Paladin (any spec) holds the eagles with Consecrate and Righteous Fury. If you don't have a paladin, you can have the MT and OT spam Thunderclap to try to hold the eagles, but they'll probably aggro onto one of the AOEers, so you'll need to be ready to heal them.
Non-elite lynx packs: I've tanked them with a bunch of damage reflecting gear such as [item]Petrified Lichen Guard[/item] with a shield spike, Thorns, [item]Stormchops[/item]. Your AOEers will have to wait for you to get some aggro because it's nowhere near as good as Consecration, and they will probably still pull aggro. Oh, and don't forget to spam Thunderclap. However, we ususally have our raid leader put on his tank gear and spam Consecrate.
Stealthed elite lynx packs: MT tanks two, OT tanks two, sheep/sleep/trap any left over. If there is not enough CC, tank more. They don't hit that hard. These groups are easy.
Admittedly a paladin tank makes ZA a lot easier. However, you can do it without one.