執筆時点で、日本語・英語・公式ドキュメント・各種Q&Aサイトどこにもまとまっていない、あるいは間違っているのでまとめました。

素朴に「AppEngineデプロイ担当者(roles/appengine.deployer)」を渡す

権限が全く不足しています。
なんでこんな命名にしたんだ。

公式ドキュメント

こちらによると、

があれば、gcloudからでも、新しいバージョンをデプロイできそうですね。
ですが、公式ドキュメントも誤っています。

storage.objects.listが必要なため、「Cloud Build編集者(roles/cloudbuild.builds.editor)」では不十分であり、「Cloud Buildサービスアカウント(roles/cloudbuild.builds.builder)」が必要
デプロイ後、トラフィック分割の権限が必要なため、「App Engine サービス管理者(roles/appengine.serviceAdmin)」が必要

とのことですね。

ただし、こちらの回答では時期が2020年1月なためか、「サービスアカウントユーザー(roles/iam.serviceAccountUser)」についての記載が不足しています。

GAEからVPCネットワークを利用してCloud Memorystore等にアクセスする場合、「サーバーレスVPCアクセスユーザー(roles/vpcaccess.user)」が必要になります。

以上です。
こちらで執筆時点では問題なくデプロイできましたが、自分もGCPに不慣れなため、過不足等ございましたら指摘いただけますと助かります。