One easy option is to have your environment variables listed in a file (or even the app.yaml file itself) in Cloud Storage. You can then use the cloud-builders/gsutil to retrieve this file in a build step like this:
steps:
- name: gcr.io/cloud-builders/gsutil
args: ['cp', 'gs://mybucket/env_vars.txt', 'env_vars.txt']
This will copy the file to the /workspace directory. The next build step can then populate the app.yaml file with the environment variables (or even just copy the retrieved app.yaml file to the correct path). The next and final step would the one you mentioned to deploy the app.
Note that, when executed in the Cloud Build environment, commands are executed with credentials of the builder service account for the project. You'll need to grant access to the file on Cloud Storage to that service account.