I didn't have any trouble with him, but my book says this:
Cast slow on Demon's Gate
Use Barrier and Haste on the party
The Heal materia will help with petrify attacks. If you don't have it, you will need softs
By the way, don't use poison, gravity, or earth spells. Poison and gravity have no effect and earth does half damage.