this thread is like a month old. but if you want my two cents, learning skills for the enemy skill materia is also very helpful, if only for big guard which gives both types of barriers and haste to all chars.
i'm pretty sure i finished the game somewhere around 50 too, so it can be done, but you might have to play around with your materia and equipment. also, you might want to think about switching in barret or yuffie with a long range materia in weapon. that way, you can put them in the backrow and they take less damage.
as for the battle itself, buff yourself up with big guard (or otherwise, cast haste and barrier spells) and take care of the tentacles first and kill both at once if possible, they got 10k and 8k hp respectively, so try to keep count and finish both with some strong magic, since they'll cast either stop or heal otherwise.
then just hammer the main body.
don't feel stingy with elixirs and ethers now, its the end of the game and you wont be needing them anymore, so when you run out of hp, down them.