C'est finalement assez simple, mais globalement dangereux. Si une déconnexion survenait au cours de cette manipulation, le système pourrait devenir inaccessible pour ce compte utilisateur. J'ai l'habitude de ne pas donner d'accès ssh à mon utilisateur root, donc je m'autodétruis dans un nuage de fumée bleue.

On commence par passer root, ensuite il faut modifier les fichiers /etc/shadow, /etc/passwd et /etc/group. Dans les deux premiers fichiers, il suffit de modifier le login à changer en début de ligne. Il doit se trouver une fois dans chaque fichier. Par exemple :

# cat /etc/shadow
[...]
hrhr:$1$foobar$blihblahbloh:13923:0:99999:7:::
[...]
# cat /etc/passwd
[...]
hrhr:x:1000:1000:hrhr,,,:/home/hrhr:/bin/bash
[...]

Le fichier /etc/group contient aussi un certain nombre de références à ce login.

# grep hrhr /etc/group
dialout:x:20:hrhr
cdrom:x:24:hrhr
floppy:x:25:hrhr
audio:x:29:hrhr
video:x:44:hrhr
plugdev:x:46:hrhr
hrhr:x:1000:

Ensuite on s'occupe de déplacer le répertoire home de l'utilisateur. On commence par modifier le chemin du répertoire home dans /etc/passwd. Ensuite on déplace le répertoire pour refléter ces changements.

# mv /home/oldnick /home/newnick

Et voualaaaaaaaaaa. A la prochaine connexion, le nouvel utilisateur peut être utilisé.

Update: Personnellement, je fais les substitutions à grands coups de :%s/hrhr/hr/gc dans vim, ce qui me permet de faire plusieurs substitutions par ligne sur tout le fichier. Chaque substitution doit être confirmée.
On pourrait également utiliser sed :

sed -i.bak 's/hrhr/hr/g' /etc/group