When I beat this I played with a fighter, thief, black mage and white mage. For variety I've changed my party a bit.

Fighter - Kicks Ass. Never leave home without one.
Black Belt - I've heard lots of good things about them on this forum, so I thought I'd see what the fuss is about.
Red Mage - Not so excited about this but I've never used one in this game. I get an extra healer which will be handy for a challenge like this, and also some physical damage at the start of the game.
White Mage - Essential to keep my party healthy.

Lets get going!
White