Easily.

I beat him at level 45. Go for it. Just take plenty of phoenix down because the undead on sector 11 gang up on you. You may beat Gilgamesh only to get your party pwned by a mob of skeletons before you reach a gate crystal (as it happened with me )