ERROR: (gcloud.beta.functions.deploy) ... message=[The caller does not have permission]

It would appear that the permissions changed when (perhaps) Cloud Functions went GA. Another customer raised this issue today and I recalled your question.

The Cloud Build robot (${NUM}@cloudbuild.gserviceaccount.com) additionally needs to be a serviceAccountUser of the ${PROJECT-ID}@appspot.gserviceaccount.com account:

NB While the Cloud Build robot local part is the project number (${NUM}), the appspot robot local part is the project ID (${PROJECT})

Please try:

PROJECT=[[YOUR-PROJECT-ID]]

NUM=$(gcloud projects describe $PROJECT --format='value(projectNumber)')

gcloud iam service-accounts add-iam-policy-binding \
${PROJECT}@appspot.gserviceaccount.com \
--member=serviceAccount:${NUM}@cloudbuild.gserviceaccount.com \
--role=roles/iam.serviceAccountUser \
--project=${PROJECT}

Let me know!

I struggled with this too after reading quite a bit of documentation. A combination of the above answers got me on the right track. Basically, something like the following is needed:

PROJECT=[PROJECT-NAME]

NUM=$(gcloud projects describe $PROJECT --format='value(projectNumber)')

gcloud iam service-accounts add-iam-policy-binding \
${PROJECT}@appspot.gserviceaccount.com \
--member=serviceAccount:${NUM}@cloudbuild.gserviceaccount.com \
--role=roles/iam.serviceAccountUser \
--project=${PROJECT}

gcloud iam service-accounts add-iam-policy-binding \
    ${PROJECT}@[INSERT_YOUR_IAM_OWNER_SERVICE_ACCOUNT_NAME].iam.gserviceaccount.com \
    --member='serviceAccount:service-${NUM}@gcf-admin-robot.iam.gserviceaccount.com' \
    --role='roles/iam.serviceAccountUser'  

Also, I added the "Cloud Functions Developer" role to my @cloudbuild.gserviceaccount.com account via the IAM Console.

According to Cloud Build documentation, for Cloud Functions you have to grant the "Project Editor" role to your service account.

But, Cloud Functions documentation states that alternatively to using the Project Editor role, you can use "the Cloud Functions Developer role [but you have to] ensure that you have granted the Service Account User role". Regarding Service Accounts, it indicates to have "the CloudFunctions.ServiceAgent role on your project" and to "have permissions for trigger sources, such as Pub/Sub or the Cloud Storage bucket triggering your function".

Due to those considerations, my understanding is that the documentation omitted to specify all the roles your service account would need and went directly to indicate to grant the Project Editor role.