I only used cloud and this strategy. It takes FOREVER but it makes the battle easy. Basically you need to master Knights of the Round, Final Attack, and HP/MP Absorb. You'll also want W-Summon and Mime. Link both HP and MP absorb to KOTR, make sure you have Final Attack > Phoenix. Kill off both of your party members and go in. He'll throw the tentacles into the ground right away and the basic strategy is just throw some KOTR at him. After every one you do, you'll be healed and your mp will be refreshed. This method takes a while, I was making sandwiches while doing the battle... it's pretty easy.