Help, if anyone can. This is a question for tacticians and strategists.

Use Inquisitors to disrupt his counter. In general, position ranged units behind shields and, on the first turn, try to eliminate the mages before the Fire Elemental appears. Leave one slot for a single unit to counterattack, so you can clear out any Gargoyles that fly in, although it might be difficult. Overall, it's definitely possible (by the way, what version of Heroes are you playing? I assume it's not 3.0). Also, consider using skills; you might have luck or morale available, as well as attack and ranged attack skills. A Fire Elemental or a Shockwave spell can really mess things up, and shields are also annoying (this is based on older versions, as I mentioned, and doesn't seem to be 3.0).