1)Keep on fighting clans,the mythril weapons(mythril gun,mythril brand and etc)that will teach combos are randomly obtained.
2)list of possible Ultima skills
Ultima shot(for hunters):from 7th heaven,can be found after recruiting Shara(correct me if im wrong)
Ultima charge(for mog kinghts):from materia blade.Use sensor and then steal from mog knight in story mission gift day.
Ultima masher(for assasins): from zanmato,sorry,i forgot where to get this weapon.
Ultima blow(for sages): from zeus mace,sorry,this one too.
Ultima Sword(for gladiators): from materia blade too.
Hope it helped.