How to recover Google App Engine's "default service account"

Unfortunately at this time, there is no way to recover the default App Engine service account. The solution is as you say creating a new project and redeploying your code there.

Should you wish to see this deletion prevented or default service account recreation made possible in the future, I strongly urge you to file a feature request on the App Engine public issue tracker while providing this example as a business case.

UPDATE: As filed by the OP, a feature request now exists on the App Engine public issue tracker as Issue 13085. Please star this issue to receive updates on its progress.

UPDATE 2: As part of the App Engine Admin API, one can now use the apps.repair API to attempt to address issues of default Cloud Storage buckets and App Engine service accounts. I would recommend trying this API before creating a new project and redeploying. I'm leaving this as an addendum and not the primary solution as it's not guaranteed to solve the issue.

UPDATE 3 It is now possible to undelete service accounts. As per the Undeleting a service account documentation, a service account may be restored if:

The service account was deleted less than 30 days ago

and

There is no existing service account with the same name as the deleted service account.

You can now recover the deleted service accounts from https://cloud.google.com/iam/reference/rest/v1/projects.serviceAccounts/undelete

you have to get the UniqueID of the service account from https://console.cloud.google.com/home/activity