As for elementals, I don't recall Zolom having any weaknesses. However, I recommend casting Bio a few times to poison it.

Equip Ifrit or Fire + Elemental in Red XIII's armor, and as many E. Skill as you can on the same person. Give him Cure, have him be the healer (no attacking! Midgar Zolom flicks away the character that hurts it most.) Have your other 2 use Bio and Cover to protect Red XIII. When Zolom gets pissed and uses Beta, Elemental protection + Red's good HP should keep him alive. At that point he can cast Beta right back and finish off the Zolom.

BTW, if you have multiple E. Skill materia on one person and a new skill is used by him, all the materia will retain it. (However, if one materia already has that skill, none of the others will learn it.)

Good luck. Like Raistlin said, save your Elixers.