The only other feasible classes I can think of are Knights, Mystic Knights (a.k.a. Dark Knights), Karatekas, Shamans, and Warlocks. Keep in mind though, that with one Shaman, you won't be able to keep up with healing the damage Dark Cloud's Flare Wave will do (you'll need two Shamans if you don't want to slowly die due to one healer not being enough). Actually, with two Shamans, the other two classes for your characters shouldn't really matter, so long as they do enough damage to not have your Shamans run out of level 7 MP or Elixirs. I think I was around level 45-55 when I defeated Dark Cloud.

Also, you probably know this, but you absolutely have to defeat all 4 bosses in the Dark World. Even if you defeat three and have 4 level 99 fully equipped Onion Knights, Dark Cloud will still be in her invincible state like her first encounter (trust me, I actually tried this out and I even have a save file of my level 99 FEOKs on the forums in the FF3 section).