A melhor chance que você tem é usar o livecd, mas para isso você precisa de acesso físico ao servidor.
Você precisa montar essas partições de alguma forma e remotamente não tem escolha.
Não pense que há outras opções. Se você pode ter acesso físico a ele, use o LiveCD para inicializar um desktop, monte seu HDD e em um tipo de terminal:
sudo nano <pathtoyourmounteddisk>/etc/passwd
Procure uma linha como esta:
root:encryptedpasswordgoeshere:0:0:ALL,ALL:/:/bin/sh
altere para:
root::0:0:ALL,ALL:/:/bin/sh
Reinicie
sudo restart
Agora você deve ir para o modo de usuário único e poder alterar a senha do root.