You really have to level in this game, but go ahead and do it while you are training materia and levels. It's a lot better and more satisfying if you do two things at once.