I think he has a set attack pattern, though I can't remember it anymore.

Don't use and Overdrives like other people have said or Steal, since it causes Nemesis to counter with Ultima. Since he only counters Overdrives, use Quick Hit and abuse it. Since Quick Hit usually makes it so you get another turn, you will most likely use this as your main form of attack.

Nemesis' attacks are powerful, and they will most likely kill you because they can still do more than 9999 damage even with 255 Defense and 255 Magic Defense (Though you may be able to survive with Break HP Limit, Protect, or Shell). Armageddon always does 99,999 damage by the way. So when he's about to attack, use Auto-Life on your characters.

You can also use the Aeon Shield trick where you summon an Aeon right before Nemesis attacks and then he will most likely kill the Aeon, wasting his turn, allowing you to attack again.

If all else fails, use Zanmato.