I had the same problem. If I remember right (and sorry if I don't, the last time I completed this game was around 3 years ago), I left Ramza as a Squire, equipped with the strongest weapon I had (which happened to be an axe) and used Jump to attack him from far away. I took Velius out in a couple of hits.