(SPOILER)Paladin Shield is the only other way to get Ultima. Error in the wording of your question!

Oh and you get the Paladin Shield by fighting 256 battles with the Cursed Shield equipped. You can get the Cursed Shield in Narshe in the World of Ruin. It teaches Ultima x1.