If you're not happy with leaving an older version somewhere, then simply open the file at
/var/lib/cloud/seed/nocloud-net/user-data, and change your hostname at the line:
It will then set
/etc/hostname to the new value and will remain consistent across reboots. This will remove all traces of the previous hostname and in the event that
preserve_hostname is either reset or ignored for some reason, you still won't lose your new hostname.