Jenova Decay is rough. My recommendation is, bring Vincent - Vincent's innate will heal him even while zombified. If you have sufficiently leveled elemental materia, hooking everyone up to absorb lightning or fire lets you use Beta/Trine as appropriate as strong team heals. Decay is mostly a gradual grinder though - her actual damage output is pretty bad. Also, don't use Level 5 Suicide. Maybe try it once, if you saved right beforehand, just to see what happens - it's pretty good.
And yeah for phys characters, Elemental+Holy or Elemental+Earth is good for damage, if you can spare it after making sure everyone absorbs an element for healing.
I ended up just powering through without any elemental healing and hoping that my whole crew wasn't zombified too fast. I got a bunch of lucky Yeahs with Tifa (entered with full limit, and got another one right before she died) that helped me scrape by.
I just got to part two, and Barret and Cait are waaaaay behind, and I used all my attack items on the boss immune to physical damage, so now I'm stuck on an embarrassing fight with two soldiers after the execution thing. I've never touched Cait because I hate his design and character. Barret I just think has an underpowered skill compared to the rest of the cast. Aeris and Tifa are my main party just for the utility, but Yuffie is so busted it's hard not to put her in any difficult fight I have trouble with.
I do have Beta but I was never good enough to win against the zolom. I'm still using lvl 2 materia so when I break out, I think I need to really buckle down and grind materia.
What happens if you suicide Jenova though? I imagine it would just Recover no? I found out the hard way that Sephiroth absorbed death element after I found a kaiser knuckle right before him and put it on Tifa and her counterattack kept "instant killing" him for full HP. -_-
EDIT: I forgot to mention. You absorb an element by maxing out Elemental right then pairing it right? Or is it maxed out Fire Matera+Elemental?