Yes, there was something obvious that I was missing.
 Systemd is all about concurrent start of services, so the cloud-init script is
run at the same time the apt-daily.service is triggered. By the time
cloud-init gets to execute the user-specified payload, apt-get update is
already running. So the attempts 2. and 3. failed not because of some namespace
magic, but because they altered the system too late for apt.systemd.daily to
pick the changes up.
 This also means that there is basically no way of preventing
apt.systemd.daily from running -- one can only kill it after it's started.
This "user data" script takes this route::
#!/bin/bash
systemctl stop apt-daily.service
systemctl kill --kill-who=all apt-daily.service
# wait until `apt-get updated` has been killed
while ! (systemctl list-units --all apt-daily.service | fgrepegrep -q dead'(dead|failed)')
do
  sleep 1;
done
# now proceed with own APT tasks
apt install -y python
 There is still a time window during which SSH logins are possible yet apt-get
will not run, but I cannot imagine another solution that can works on the stock
Ubuntu 16.04 cloud image.