I created a GitHub repo to answer this problem. It uses two templates to separate the state of the state-holding bucket and the state of everything else. Since the state of the state bucket will rarely change, this state will be held locally - basically in your Google Cloud Shell storage (or similar) and possibly backed up informally (for example, to Google Drive). Then, the state of the rest of your infrastructure goes into that state bucket.

This does create the problem of having the state bucket name be (possibly) dynamically generated in one template and then used again to terraform init another, but I used Google Cloud Compute metadata resources to temporarily hold this information, and a wrapper around terraform init to add it to the backend configuration of the template for the rest of the infrastructure.

More details are available in the repo's README document.