Doom Gaze is a random encounter in the World of Ruin, you encounter him while flying around on your airship, sometimes he can be a REALLY rare encounter, just keep flying around all over and eventually you'll run into him, after a certain amount of damage he will escape but he will never heal the HP you take from him each time you fight him, so just keep dealing the damage and with enough encounters he'll go down.

The Alexander esper is found after you complete the World of Ruin Cyan side quest in Doma Castle. (Sleep there with Cyan in your party and complete the event) Once the event is over, go to the throne room of the castle and Alexander will be on the throne.

Hope this helps, good luck!