Posting this as an answer as it seems that my edit (we work together) was silently rejected, and a comment is too limited. This is not an answer but that is expanding the question.

Simpler example with a single http request. It seems that the JSON API is simply not working outside the API explorer. The XML/REST API works and returns a list of files in the bucket.

credentials = AppAssertionCredentials(scope='https://www.googleapis.com/auth/devstorage.read_write')
http = credentials.authorize(httplib2.Http(memcache))

bucket_name = app_identity.get_default_gcs_bucket_name()

# This works (200 with list of files in the content)
request_url = 'http://commondatastorage.googleapis.com/' + bucket_name
response, content = http.request(request_url, method="GET")

# This doesn't work (403, Access not configured)
request_url = 'https://www.googleapis.com/storage/v1/b/' + bucket_name + '/o?alt=json'
response, content = http.request(request_url, method="GET")

# This doesn't work (403, Access not configured), the key and project id header seem useless.
request_url = 'https://www.googleapis.com/storage/v1/b/' + bucket_name + '/o?alt=json&key=' + API_KEY
response, content = http.request(request_url, method="GET", headers={'x-goog-project-id': PROJECT_ID})

Also, looking at the code of AppAssertionCredentials, we can see:

  kwargs: optional keyword args, including:
    service_account_id: service account id of the application. If None or
      unspecified, the default service account for the app is used.

self.service_account_id = kwargs.get('service_account_id', None)

Passing anything as service_account_id argument results in an exception:

Traceback (most recent call last):
  File "/base/data/home/apps/.../1.37.../backup.py", line 61, in get
    response, content = http.request(request_url, method="GET")
  File "/base/data/home/apps/.../1.377.../oauth2client/util.py", line 132, in positional_wrapper
    return wrapped(*args, **kwargs)
  File "/base/data/home/apps/.../1.37.../oauth2client/client.py", line 491, in new_request
    self._refresh(request_orig)
  File "/base/data/home/apps/.../1.37.../oauth2client/appengine.py", line 197, in _refresh
    raise AccessTokenRefreshError(str(e))
AccessTokenRefreshError

I have tested to pass the value returned by app_identity.get_service_account_name(), that doesn't work. (even though the documentation says it will use "the default service account for the app" if it is not set).

I have tested to pass the service account email found in the developer console that has the form: 3....-v0....@developer.gserviceaccount.com. Same token exception.

So, why are we getting a 403 Access not configured when the Cloudstorage JSON API is clearly enabled under our api/services?

And why is passing a service_account_id to AppAssertionCredentials failing with a AccessTokenRefreshError?

Edit:

The solution was ridiculous: turn OFF the Google Cloud Storage API, and turn it back ON.

I assume that the app was a "legacy" app, and doing so made the last bullet point 12 work here: https://developers.google.com/appengine/docs/python/googlecloudstorageclient/activate