The skinmaker mod lets you create custom skins at run time, and apply them without restarting the server.

It should be noted that the mod author doesn't recommend this for servers.