I was stuck on that fight FOREVER!
Eventually I just got pissed and made a new game... lol
What I did was basically have 2 BLMs, Ramza on Knight (Dual Wield), a SMN, and Mustadio as Engineer.
I then had the BLM's Meteor the shit out of Velius, Ramza slash his brains out, the SMN use strongest Summons, and Mustadio shoot him from afar. I kept ALL of my members apart from each other at all times, so AoE moves wouldn't hit all of them. I think I had some Angel Rings to keep them up after dieing. Not sure. After that he went down no problem lol.
XI Wiki

