Keep doing it through CQ. Probable cause of failure is a race between your git cl push and CQ.

I am having the same issue today, already tried for the 7th time in ~3 hours.

I need to merge in few hours to catch beta. PTAL at the problem.

FYI: I tried the non-drover way in my last two attempts, got this error message, even in my synced git client.

...
 1 file changed, 2 insertions(+), 2 deletions(-)
error: failed to push some refs to 'https://chromium.googlesource.com/chromium/src.git'
hint: Updates were rejected because the remote contains work that you do
hint: not have locally. This is usually caused by another repository pushing
hint: to the same ref. You may want to first integrate the remote changes
hint: (e.g., 'git pull ...') before pushing again.
hint: See the 'Note about fast-forwards' in 'git push --help' for details.
Failed to push. If this persists, please file a bug.

Note that tandrii is in EMEA timezone and you might not get any help today. Please file a trooper ticket if this is urgent.

So you keep rebasing remote changes and still get that error? What ref are you merging to?

the workaround is indeed landing through CQ. git cl land no longer auto-rebase on push failure: one has to manually "git pull --rebase" and retry "git cl land".
This shouldn't be likely to happen, unless you are pushing against **master** branch.