I have just finished the game for the first time, and my party was Warrior/Monk/White Mage/Black Mage (or rather, their descendents). I didnt realise, or just plain forgot that the Monk/Master is stronger unarmed as early as Lv.10, so at some point around the Waterfall Cavern my quest became significantly easier.