I beat him yesterday, and my stats werent particulary high, attack around 60-80same with defence.
Basically he does 9999 with every attack (aside from limit break which does about 50k) so I had tidus equppied with autophoenix and autohaste. Wakka with 10,000-odd hp and rikku with auto life white magic.and just kept rikku as healer and wakka and tidus attacking, and obviously having an aeon take the brunt of his overdrive (I managed to get an Oblivion on valefor, did about 230,000)

also, yes start again