After doing some more digging, you also need to set

system_info:
   distro: arch

in /etc/cloud/cloud.cfg, as Arch includes the upstream cloud.cfg which has ubuntu set as the distro (which uses str(conf) and thus doesn't have the issue).

I'm using the NoCloud provider with

$ cat meta-data
instance-id: iid-local01
local-hostname: arch-cloud

and nothing interesting in user-data. The execution log on the server looks like this.

$ sudo pacman -Qi cloud-init | grep Version
Version         : 0.7.9-1
$ sudo cloud-init single --name=set_hostname --frequency=always
Cloud-init v. 0.7.9 running 'single' at Fri, 21 Jul 2017 17:08:18 +0000. Up 433.04 seconds.
2017-07-21 17:08:18,193 - util.py[DEBUG]: Cloud-init v. 0.7.9 running 'single' at Fri, 21 Jul 2017 17:08:18 +0000. Up 433.04 seconds.
2017-07-21 17:08:18,194 - stages.py[DEBUG]: Using distro class <class 'cloudinit.distros.arch.Distro'>
2017-07-21 17:08:18,194 - stages.py[DEBUG]: Running module set_hostname (<module 'cloudinit.config.cc_set_hostname' from '/usr/lib/python2.7/site-packages/cloudinit/config/cc_set_hostname.pyc'>) with frequency always
2017-07-21 17:08:18,194 - helpers.py[DEBUG]: Running config-set_hostname using lock (<cloudinit.helpers.DummyLock object at 0x7fe51cf5d690>)
2017-07-21 17:08:18,194 - cc_set_hostname.py[DEBUG]: Setting the hostname to arch-cloud.localdomain (arch-cloud)
2017-07-21 17:08:18,195 - util.py[DEBUG]: Reading from /etc/hostname (quiet=False)
2017-07-21 17:08:18,195 - util.py[WARNING]: Failed to set the hostname to arch-cloud.localdomain (arch-cloud)
2017-07-21 17:08:18,197 - util.py[DEBUG]: Failed to set the hostname to arch-cloud.localdomain (arch-cloud)
Traceback (most recent call last):
  File "/usr/lib/python2.7/site-packages/cloudinit/config/cc_set_hostname.py", line 47, in handle
    cloud.distro.set_hostname(hostname, fqdn)
  File "/usr/lib/python2.7/site-packages/cloudinit/distros/__init__.py", line 84, in set_hostname
    self._write_hostname(writeable_hostname, self.hostname_conf_fn)
  File "/usr/lib/python2.7/site-packages/cloudinit/distros/arch.py", line 120, in _write_hostname
    util.write_file(out_fn, conf, 0o644)
  File "/usr/lib/python2.7/site-packages/cloudinit/util.py", line 1747, in write_file
    content = encode_text(content)
  File "/usr/lib/python2.7/site-packages/cloudinit/util.py", line 154, in encode_text
    return text.encode(encoding)
AttributeError: 'HostnameConf' object has no attribute 'encode'
2017-07-21 17:08:18,198 - util.py[WARNING]: Running module set_hostname (<module 'cloudinit.config.cc_set_hostname' from '/usr/lib/python2.7/site-packages/cloudinit/config/cc_set_hostname.pyc'>) failed
2017-07-21 17:08:18,199 - util.py[DEBUG]: Running module set_hostname (<module 'cloudinit.config.cc_set_hostname' from '/usr/lib/python2.7/site-packages/cloudinit/config/cc_set_hostname.pyc'>) failed
Traceback (most recent call last):
  File "/usr/lib/python2.7/site-packages/cloudinit/stages.py", line 776, in _run_modules
    freq=freq)
  File "/usr/lib/python2.7/site-packages/cloudinit/cloud.py", line 54, in run
    return self._runners.run(name, functor, args, freq, clear_on_fail)
  File "/usr/lib/python2.7/site-packages/cloudinit/helpers.py", line 187, in run
    results = functor(*args)
  File "/usr/lib/python2.7/site-packages/cloudinit/config/cc_set_hostname.py", line 47, in handle
    cloud.distro.set_hostname(hostname, fqdn)
  File "/usr/lib/python2.7/site-packages/cloudinit/distros/__init__.py", line 84, in set_hostname
    self._write_hostname(writeable_hostname, self.hostname_conf_fn)
  File "/usr/lib/python2.7/site-packages/cloudinit/distros/arch.py", line 120, in _write_hostname
    util.write_file(out_fn, conf, 0o644)
  File "/usr/lib/python2.7/site-packages/cloudinit/util.py", line 1747, in write_file
    content = encode_text(content)
  File "/usr/lib/python2.7/site-packages/cloudinit/util.py", line 154, in encode_text
    return text.encode(encoding)
AttributeError: 'HostnameConf' object has no attribute 'encode'
2017-07-21 17:08:18,199 - main.py[WARNING]: Ran set_hostname but it failed!
2017-07-21 17:08:18,200 - util.py[DEBUG]: Reading from /proc/uptime (quiet=False)
2017-07-21 17:08:18,200 - util.py[DEBUG]: Read 14 bytes from /proc/uptime
2017-07-21 17:08:18,200 - util.py[DEBUG]: cloud-init mode 'single' took 0.052 seconds (0.06)