(Getting back to Zombies)
The feasibility of this depends on the strength of the Zombies. Skeletons are

3, after all... and because of them, the Sailor's Dirge is a respectable early-game threat.
I'd say put Zombies in the same category. Say, implement Zombies (as described) at

4, appearing around the same time as Orthus. This provides a scary early-game threat, but can be easily handled with certain technological advances... The Drown, for one... also, the Loyalty spell (as infected soldiers suicide on command). Later on, there are too many counters to such a thing... even with more powerful units, the countermeasures drastically reduce the threat element.
Alternately...
Zombies (different implementation) appearing fairly late in the game. Instead of units becoming weak Zombie units, have infected units gain the Zombie promotion

strength: +2, Undead, Magic Resistance, can infect other units) and join the Barbs. Also, have defeated Undead of any sort join the Zombies straight across (losing Summoned promotions, if applicable), possibly gaining similar buffs as well. (Note: The Magic Resistance is a blatant counter to the 'summon lots of things and have them fight the Zombies' trick... making Zombies a lot scarier, and more viable late-game)