I think I did so with my 4 monk playthrough but I can't remember now.

To get a job change you have to get the rat tail from the Castle of Ordeals and then bring it to King Bahumut who's on the island with two holes in it. It makes most classes better in stats and allows them to equip higher level gear and use higher level magic.