Although you may think all is lost, there is still ways to access everything. You can get to Odin's place, and from there, get Tonberry. Tonberry can learn to call shops, which means you can get new stuff. You can also find the Ragnarok around there, and use that to go to the Island Closest to Heaven, and the Island Closest to Hell, and draw high-level magic.

For the last battle, I killed off the characters I didn't want in the first battle, and then just put Aura on Squall. Abused that and Ultimecia was dead.