Você vai precisar de um Live CD, para quem não sabe o Live CD é aquele Linux que roda direto do CD-ROM, insira o CD e faça o reboot, quando iniciar o sistema você entra em modo texto com as teclas Ctrl+Alt+F1.

Em seguida digite cfdisk para verificar em qual partição o Linux está instalado, geralmente é na primária.

Digite:

# mkdir /qualquernome (criando um diretório onde será montada a partição primária para alteração do arquivo de senhas)

Monte o volume com o comando:

# mount /dev/sda3 /pasta_que_foi_criada (o "sda" é um exemplo de onde se localiza a partição primária do sistema que está instalado)

Acesse com o comando:

# vi /pasta_que_foi_criada/etc/passwd

Procure o root e apague o primeiro "x" que esteja à frente, possivelmente:

root:x:0:0:root:/root:/bin/bash

e depois salve a alteração com ESC e depois :wq

Reinicie a máquina e quando entrar novamente no sistema, abra o console e use o comando:

su -

Você estará logado como root, para criar a nova senha é só usar o comando passwd e inserir a nova senha.