As I remember, there is a possibility to mark cheater and griefer in steam. Some developer look at this and don´t sell their games to them. But I just have heard about that ... I´d never tried myself.
I´m not sure if I understand your post correctly. He´s just on your server while no GM is on? How does he know? How can a new character kill experienced players? And how did ya tried to ban him without any GM ingame?
Did you think about an server-Password? Ask your admin.
Banning People should be just the last possible step. Presenting them some "friendly" bears
(no problem for GM´s) is my personel favorite in boring times. Deleting their horses while in a high speed ride is another nice one. So just try to grief the griefer.
And yeah, Lif has to be payed for every Steam-account. So make sure, your don´t harm al the new player on your server just because they might eventually perhaps call someone names.