Yes, they should cost a little bit but if you can't add the 0 food for zombies, you can increase a little in the Gold and Lumber Costs. I defeated Arthas' lich and the taurens by using only Zombies

They are awesome, but one thing. Maybe Mal'Ganis met some Night elves (If possible only) because when Arthas came in Kalimdor, he showed up to Illidan. So maybe when Illidan and Arthas were talking, maybe Mal'Ganis could sneak up into their conversation then disappeared. Like for example
Arthas said to Illdian "Illidan, the Skull Of Gul'Dan is guarded by Demon Gates, if you destroy those demon gates and acquire the power of the Skull, you will be able to defeat tichondrius"
Then Mal'Ganis appeared by teleporting. Just like dreadlords do..
"Yes, but I will not let you obtain it easily" mal'ganis said
"My forces is here, and I am sure that you must not interfere with lord archimonde's plan" mal'ganis said
Then in that mission, Arthas said :
"Mal'Ganis! How did you get through Ammemnar's forces!"
"That lich is dead, so must be you"
"What are you doing here? You must be there with your Archimonde!"
"I am here of making sure that no one interrupts with lord archimonde's plan" replied mal'ganis
"I'm giving you a chance to walk away Arthas, you summoned the burning legion, you earned the legion's trust, and now you are going to stop it? You are probably wasting your efforts in summoning the legion, boy" Said mal'ganis
"If you could waste enough time for this!" shouted Illidan then hitted Mal'Ganis with his blade
Then mal ganis disappeared
It is most likely that Arthas continues his plan of stopping the legion, Mal'Ganis could chase him but Illidan is blocking the path. So... Mal'Ganis met with Tichondrius and warned tichondrius. Tichondrius said he will handle illidan's forces, and mal'ganis would go chase arthas.
Then that chapter must be an interlude...
Done, I hope this is possible, but if you would like to make this interlude, I would likely said that you must fix a little bit in the dialogues XD