I'm not 100% sure on this, but if you got Odin on Disc 2, Gilgamesh becomes available on Disc 2 in the battle with Seifer at Galbadia Garden.