It's fácil. Basta clicar no ícone Gear (localizado no canto superior direito da tela), abrir "Sobre este computador" tela (localizada no ícone Gear ) e editar "Nome do dispositivo".

Ou, em um terminal, use o seguinte comando:

sudo hostname your-new-name

Isto irá definir o nome da máquina para o seu novo nome até que você reinicie. Veja man hostname` e https://askubuntu.com/questions/9540/how-do-i-change-the-computer-name para mais informações. Não utilize _ no seu nome.

**Nota***

Após um reinício, suas alterações em /etc/hostname serão utilizadas, então (como você disse na pergunta), você ainda deve utilizar

sudo -H gedit /etc/hostname

(ou algum outro editor) para que o arquivo contenha o nome da hostname.

Para testar se o arquivo está configurado corretamente, execute:

sudo service hostname start

Você também deve editar `/etc/hosts' e alterar a linha que lê:

127.0.1.1     your-old-hostname

para que agora contenha o seu novo nome de anfitrião. (Isto é necessário caso contrário muitos comandos deixarão de funcionar).

Sem Reinício

Mudar o nome da máquina ou nome do computador no ubuntu **sem reiniciar***

Editar /etc/hostname e mudar para o novo valor,

nano /etc/hostname 

Editar /etc/hosts e mudar a antiga linha 127.0.1.1 para o seu novo nome de anfitrião

127.0.0.1   localhost
127.0.1.1   ubuntu.local    ubuntu   # change to your new hostname/fqdn

Nota : li num fórum > Editar /etc/hosts e mudar a antiga linha 127.0.1.1 para o seu novo nome de anfitrião (se não o fizer, já não poderá usar o sudo. Se você já o fez, pressione ESC no menu do grub, escolha recuperação e edite seu arquivo de host para as configurações corretas)

Agora, após uma reinicialização, o seu nome de anfitrião será o novo que você escolheu.

Sem Reinício

Para mudar sem reiniciar, basta usar hostname.sh depois de editar /etc/hostname. Você deve manter ambos os seus nomes de host em /etc/hosts (127.0.0.1 newhost oldhost) até que você execute o comando abaixo:

sudo service hostname start

Nota : Acima do comando para tornar a mudança activa. O hostname salvo neste arquivo (/etc/hostname) será preservado no reinício do sistema (e será configurado usando o mesmo serviço).

sudo hostname your-new-name
sudo /etc/init.d/networking restart

Isso deve fazer o trabalho que eu acho