I first beat him with Equinas, Brachio, and... I think it was Tricera.
I know you probably despise this but Paki, Malachi, and Andrarch is a really good team despise their low LP, I beat Zongazona multiple times with it later, you just have to keep using Andrarch's team move to make them Enraged so they keep missing you, but, you have a 98% chance of loosing Paki even enraged after a long time, but they almost always keep missing Malachi and Andrarch, (I know I'm spelling them wrong XD) Anyway, they are level 20, but that's also a good team others...
T-rex lord, Andrarch, Giganto.
Alectro, Kaishin, Equinas.
Equinas, Kaishin, Toba
Teffla, Giga Spinax, Stego.
Ryden, Equinas, Toba
Camara, Toba, Ryden
Camera, Stego, Teffla