My characters had 40000 Hp+ (Auron, Tidus, Yuna) with almost the entirely Sphere Grid completed. I killed all the monsters in the arena, including Shinryu (this was tough because my Rikku was weak as hell) and Nemesis (after a dozen billion tries).

For Fenrir, you do need speed. Use Tidus, a must, and Wakka. Yuna should always be in the party, so she can help you out with healing, and summon Magus Sisters when things get rough.