I tried many ways and the hostname kept getting reset back to the previous value. Turns out there are two steps to changing the hostname permanently on Ubunut.
Firstly, update preserve_hostname in /etc/cloud/cloud.cfg
preserve_hostname: true
Secondly use hostnamectl to change the hostname
sudo hostnamectl set-hostname new-host-name
Now when we reboot, the hostname will stay as new-host-name