For this other-worldly Nemesis, bring along a Spiritmaster with Fairy Ward and a team of powerful physical and magic characters; alternatively a team of spell-casters with Pierce Magic Defence (Black Mage) will do fine.
Leviathan has two forms–the first is its "High Altitude" form, which evades all physical attacks.
If you have any physical characters, have them Default during this phase, while your spell-casters dish out the pain with Deux Ex, Meteor or Thundaja. In this form, Leviathan uses Bite to hurt one character and Blizzaja --the ultimate Water spell–to rain havoc on your party. It also uses Envy to drop your party’s physical and magical defences, as well as dispel your buffs.
Abate Water (White Mage) would do nicely on your characters and the Iceflame Shield (nullify Water) on your healer. The decreased defence from Envy isn’t too bad if you have a Salve-maker compound a Giant’s Draft to double everyone’s HP. If you have Conjurers, they can invoke Deux Ex to max out their Magic Attack again.
After three attacks, Leviathan will use Magic Resist Form to switch forms–its second form no longer evades physical attacks, but has maximum Magic Defence. If you brought physical characters, now is the time for them to Brave like crazy. Otherwise, if you have Pierce Magic Defence, your spell-casters can continue their magical onslaught without a problem.
During this stage, Leviathan uses The Last Light to blast your party or Consume Life to damage your party and cause instant Death or Doom. Definitely have your Spiritmaster cast Fairy Ward around this time to keep your party safe (note that Envy dispels Fairy Ward).
Again, after three attacks in this form, Leviathan will use High Altitude to switch back to its first form and the cycle repeats. Near the half HP mark, Leviathan will start going mental and Brave twice, unleashing three moves in one turn and going immobile for two.
At this point, your Spiritmaster’s elemental protection won’t help, as High Altitude Leviathan always uses Envy when it Braves, dispelling your buffs, so just Default to survive the blizzard. For Magic Resist Leviathan, you definitely want Fairy Ward to survive two lots of Consume Life and the Templar’s Rampart or Ninja’s Utsusemi to block out one attack.