You should have Celestial Weapons, stats nearing 255 (200 at the very least), and armor with Auto-Haste. There are three main ways to go about beating him; I call them the Tank method, the Revive method and the Yojimbo method.

For the Tank method, have two characters to do the attacking, and one character (Lulu if you have her CW, otherwise just make a weapon with BDL, Magic Booster, and One MP Cost) to cast Auto-Life and heal after Armageddon. Pump up your fighters' HP to around 30,000 or higher, allowing you to take anything he dishes out except Armageddon. Make sure all characters have Auto-Life when he attacks, in case he uses Armageddon. This method is less effective because you spend too much time casting Curaga, and it would be a waste if he uses Armageddon.

The Revive Method is to continually cast Auto-Life on yourself, and attack whenever you have a free turn. The advantages here are that you don't need BDL, and never have wasted turns. The only possible disadvantage is running out of MP, (which will happen surprisingly fast unless you have Yuna and Lulu in your team), but you can use Osmose on Nemesis to build it back up.

The third method is just pay Yojimbo a crapload of gil.