Google Compute Engine Virtual Machine: Unable to connect via SSH using any method

When using SSH to connect to my VM, the process hangs indefinitely when the VM asks the metadata server for an authentication token. This happens when using a browser shell (the SSH button on the VM tab) and also when using Cloud Shell. This is the output from the serial console, which I am able to connect to.

serialport: Connected to peerless-rite-139921.us-central1-b.wrangl-reload port 1 (session ID: 305e0a35ea71dec437aaae0302eb479de1d20562, active connections: 1).
Jul 25 18:38:34 wrangl-reload dhclient[567]: DHCPACK of 10.128.0.3 from 169.254.169.254
Jul 25 18:38:34 wrangl-reload dhclient[567]: bound to 10.128.0.3 -- renewal in 37979 seconds.
Jul 25 18:46:11 wrangl-reload collectd[692]: write_gcm: Asking metadata server for auth token
Jul 25 19:19:47 wrangl-reload systemd[1]: Starting Daily apt download activities...
Jul 25 19:19:54 wrangl-reload systemd[1]: Started Daily apt download activities.
Jul 25 19:19:54 wrangl-reload systemd[1]: apt-daily.timer: Adding 11h 43min 24.702830s random time.
Jul 25 19:19:54 wrangl-reload systemd[1]: apt-daily.timer: Adding 2h 56min 56.298278s random time.
Jul 25 19:21:11 wrangl-reload collectd[692]: write_gcm: Asking metadata server for auth token
Jul 25 19:53:11 wrangl-reload collectd[692]: write_gcm: Asking metadata server for auth token
Jul 25 20:51:11 wrangl-reload collectd[692]: write_gcm: Asking metadata server for auth token

In addition, if I try to SSH from my Mac using Terminal using a public key I created locally, I get Permission denied (publickey).
I have tried accessing the server with SSH from other VMs, which also resulted in Permission denied (publickey).

The disk is not full.
I have tried using a startup-script in metadata, but that too fails.

The firewall rules are project-wide and we have two other VMs in the same project, which are both reachable with SSH.