You won't be able to beat him when you first encounter him unless you've been levelling up a lot. Just come back and get him later at around level 40-45-- that's what I did and I wiped the floor with him.