Great campaign so far! Mission 4 is the hardest mission I've ever played, in any custom campaign (Including Tomoraider's & Tunro's campaign on hard!) This is my strategy for it, on hard difficulty:
Army composition, Golems, warlocks and some towers. Here is why:
-Warlocks: Fireball stun and damage is insignificant. Unholy frenzy is good on golems. Get about 4 of these.
-Golem: Good tank and great damage! They have heavy armor, so magic damage is their only weakness. Luckily, there is a lack of magic damage in this chapter. Get as many as you can of these.
-Tower: Weak against vindicators and elites because of the defend ability, great against everything else!
-Grunt: Good tank and good damage, but is strictly weaker than golems.
-Catapult: Great damage against buildings and units, but the problem is they have 425 hp, and get focused down too fast, so they don't last long in combat.
-Axethrower: This clown-looking unit serves only one purpose, and that's to make you laugh at how useless it is. The majority of the enemy damage types are melee, and half of them have the defend ability, causing this unit to die too fast and barely inflict any damage.
-Shaman: No use for purge. Lighting shield may be good against enemies, but this strategy relies on mass melee units, which means lighting shield will hurt our units too.
-Necrolytes: Raise dead is useless because the enemy ignores the skeletons and goes straight for your non-summoned units (In normal difficulty, enemies didn't ignore the skeletons). At max mana, can cast chain lighting twice, but the damage is not significant in comparison to mass golems. Combat lasts about 1-2 minute(s), in that time, golems will do more damage than chain lighting. Dies quickly to catapults and archers, so their 'tankiness' is weak. Also, damage against buildings is terrible compared to golems.
First off, put the game on the slowest difficulty. If you think this is cheating, then continue off with normal speed. Here is how the combat strategy will work:
Whenever you're in combat, any time you see a golem with less than half hp, run them to the healing fountain. This is why having slow speed is good, as you can react faster to save your golems. In combat, get Grofzag right in the middle and use howl of terror. Hurl boulder when you see starfall come down. Put a point into Command Aura. Zairmak should use sleep and soul burn in the following priority: priests> knights > vindicators. Don't bother casting it on elites, as it doesn't last long. Put points into the sleep skill. Also, right before engaging the enemy, warlocks should cast unholy frenzy on all units, including heroes. Keep warlocks away from the combat, don't let them fight, else they'll get killed. Only bring them back in to cast unholy frenzy when it runs out. I like to put warlocks in control group 3, and the rest of the units in 1 and 2. Priests will cast dispel to get rid of unholy frenzy, so use soulburn and sleep to shut them up. Also, if you only attack move with your golems, you'll notice that they path block each other because they stop too early to attack the enemy. What you want to do is move forward enough with your golems so they're right in the middle of the enemy units. This will ensure every golem is attacking, maximizing dps.
Now, the mission starts. Immediately make 7 peasants for lumber harvesting, research the melee weapon and shield upgrades, and que up 4 warlocks and golems, until you have 50 food. Help your ally defend on the west side. After that, immediately run south west of your base, where the blue knights are. Get Grofzag to come close to one of the knights to lure 4 of them out of the tower range. Kill these 4. There will be 6 more knights left, so lure those out the same way, fight them outside of the tower range. Now, unholy frenzy the golems and focus down the blue barracks, taking care not to lose any golems. Finish off the towers and the remaining blue units. By this time, one of the enemies will be heading to your base, so run back to defend it. While your units are running back, get about 4 peons and start building towers right outside the ramp leading to the purple base as shown:
You also want to make 6 burrows and 2 barracks near these towers. I like to hotkey the 2 new barracks and the 2 barracks in our base to control group 0. After defending against the attack in your base, run to the constructed towers and start getting out those golems, going past 50 food. At this point, purple will attack, with no hero. Let them come close to the towers before engaging with golems. This fight should be a piece of cake. Now, you had 2 necrolytes given at the start of the mission. Start summoning skeletons from purple's corpses, put it on auto-cast to make it easier, this is very important, as you'll soon see why. In the mean time, run Zairmak up the ramp and boop one of their towers. Their entire army, including their hero, should come chasing Zairmak, so lure them all to the towers. If you don't summon skeletons, then purple's corpses will remain. Their hero has the resurrect ability, and we don't want him bringing back his units. Their hero also has the shockwave ability, making short work of your towers, so what you need to do is cycle between sleeping, soulburning and stunning (in that order) their hero so he doesn't have a chance to cast it. You need to make sure the towers avoid hitting their vindicators, as they have defend. So have them focus knights, grey wolves, archers, or priests instead. I just hotkey the towers to control group 8 and que up targets that were not vindicators. Eventually his entire army will fall and you should not have lost any golems (If you're playing on the slowest speed). Remember to keep queing up those golems. You should be near 80 food at this point. Also, you don't need the necrolytes anymore, so kill them. Save here. Now, there is a choke point in purple's base, which is bad news for us because all our units are melee. So, what you need to do is move every golem past this choke point, and then let them attack. We need destroy the altar first, then the barracks (on the north side, avoid the south barracks!), then the castle, then the remaining units. Consider reloading if their hero revives before you destroy their altar. Have 1 golem dedicated to kill any workers trying to rebuild production structures. Stay away from the south side of their base, otherwise you'll aggro the units stationed there. You will encounter Ares Knights, which are buffed up versions of knights. Soulburn and sleep these. You want to take out the south barracks last. You will lose a few golems.
Before purple falls, your main base will get attacked by grey and light blue at the same time! We have to let our base fall, so select all your peons and bring them close to your towers. Once purple's production structures are gone (leave the armory or lumber mill alive so the mission doesn't end), we will construct our new base in purple. Congratulations, You have passed the hardest part of the mission!
There are tomes in all of the town halls of the enemy bases (except grey), so it's your choice if you want to grab those. If you do, then we'll need to retake the middle part of the map, for the goldmine, and the healing fountain. After purple falls, bring a peon to construct a town hall in the middle. Kill your units to drop down to 80 food, we will be holding out middle for a long time, and you'll see why shortly. Make a catapult and move it northwest, up the ramp. Immediately up the ramp, start destroying the trees towards the west side. You want to cut up a path towards light blue's base, like so:
The normal path to light blue has a choke point, and we've seen how difficult that is to deal with. Get up to 100 food (kill your catapult, its not needed). Now, what you want to do is position your golems at the left end of this path. Get Zairmak to poke one of their towers, and run back towards your base. You want to lure light blue's army just up the ramp leading to your base. We have now divided light blue's army! So move up your golems and start killing their units. Focus down the production structures first, like we did with purple. Zairmak has probably been taking a beating, so teleport him to the main army. Light blue should fall at this point. Your middle base will probably get attacked by grey, but let that fall. One thing to note about enemy AI is once your town hall has fallen, they will satisfied and retreat back to base. Now, rebuild your base in the middle, and make a town hall in light's blue base. The other 3 bases, red, teal, and blue are much easier to destroy compared to purple and light blue, so I see no need to make a strategy for them. Just use the golem and warlock combo and they should fall with ease.
Good luck!
P.S. If anyone else has beaten this on normal or hard, I would be interested in hearing their strategy (without cheats).