gsutil lson a Compute Engine VM, I received a stack trace like this:
It turns out that gsutil doesn't like Python installed from Linuxbrew. It really wants to use the system Python. The following works fine:
Traceback (most recent call last):
ImportError: No module named google_compute_engine
Easy enough to fix. Nobody else had documented trouble with this configuration so here you go Internet.
env CLOUDSDK_PYTHON=/usr/bin/python gsutil ls ...