Okay, so here's what I suggest.
The team should be Monk and three black magi. You will want to use the ship game at least twice (possibly three) to get yourself a Cockatrice Claw (can't recall what rank awards them). With frame advance you could easily beat the puzzle in 3 seconds or less. You'll want to use this on Astos to kill him in one turn. The time gained should outweigh the time spent. You'll probably also want to get two Blue Fangs to use on the Piscodemons. I suggest having the Magi use them and I suggest fighting 4 of them to get more exp without spending any time fighting random crap. Naturally this should be tested to see if any time is saved at all.
Later on in the game most of your troubles can be avoided by taking a trip to the caravan and investing in some of the stat boosting items he sells. Instead of spending god knowns how many fights grinding you could spend one turn having your team use Giants Tonic to increase your max HP by 200 a pop. I actually see no real reason to get into any random fights in the whole run. In fact, aside from Temper, Haste, and possibly Sleep (for the 9 pirates) I see no reason for any other spells because they do so very little damage and take so long to cast.
You could check out my guide at GameFAQs for some more possible ideas.
http://www.gamefaqs.com/portable/gbadvance/file/920240/35878
Aside from covering all the bosses up to class change in the lowest level it also lists every item in the game that can boost stats and exactly by how much they boost them in case you don't already know. On that note, I highly suggest that you do NOT class change because it doesn't help at all with levels as low as you'll undoubtedly have.
Trust me when I say that optional level grinding isn't needed. I've beaten the game with a solo lowest level thief unclasschanged and even Chaos posed little threat with the proper planning. With three BMs to back you up you'll also not need to worry about assloads of curing like a solo challenge so Chaos should drop in about 5 to 6 well manipulated turns.
Oh, and have you figured out how to abuse the RNG in and out of battle yet?
