Even Nature's Revolt doesn't help much - haven't tried it yet, but if the Civ4Wiki is correct, it gives:
For the Barbarian State:
Each Goblin Worker is replaced by 3 Wolves.
Each Goblin is replaced by 3 Lions.
Each Orc Spearman is replaced by 3 Lions.
Each Lizardman is replaced by 3 Tigers.
Each Orc Axeman is replaced by 3 Bears.
Note that each of these new units gains the Commando promotion
Note that it gives mostly the more common animals: Wolves, Lions and Bears. It also gives Tigers, but: NO GORILLAS.
I've yet to build a Grand Menagerie, though I've often tried. It's always either a Gorilla or a Tiger that's missing.
The one time I actually had all the required animals (on a Huge Terra Map), the game crashed before I could get the lone Tiger I found on a barbarian continent back to my capital