My favourite way to level "legitimately" is to enter/exit the dungeons a few times; this gives a much stronger feeling of accomplishment than just using the Select/Cancel trick, which I've always found rather dull and boring, TBQH - it feels like the characters are using steroids to become stronger or something, and that they aren't strong "for real".
You can also sort of "level up" rather normally against certain enemies - the Captains in Phin are relatively high-rank, so you can easily boost stats by just fighting them normally.
They are much easier in the Origins version though, since Life always works there; in the NES original it's wise to raise it to about LIFE 4 or LIFE 5 first.
That's EXACTLY what I do!
I guess it's easy to decide on these jobs though, since the main characters' stats and equipment kinda encourage you to do so (Maria's high Intelligence etc).