Update: As it turned out, deactivating background data for Play Store is not enough. I updated the instructions below to completely deactivate Google Play Store instead.
As far as I know, Google Play Services is not a regular app. That’s why switching off the regular “automatic updates” setting won’t make a difference. Google Play Services is aggressively and automatically updated by the Google Play Store whenever it’s possible, because it’s so “mission critical” to many other apps and Google doesn’t want it to get old on phones where automatic updates are disabled. It’s on the border of being morally sound I guess, but in our case it’s clearly contraproductive.
Having searched the Internet, one of the rare possible workarounds in our case is to disable Google Play Store and stop using it until the issue is fixed.
Steps:
-
First open Google Play Store app info (Store, not Services!):
Long press Play Store icon → little (i) sign -
Now disable it with the “Deactivate” button
-
Do not use/open/reactivate Google Play Store until the issue is fixed by Fairphone+Google. Deny any prompts for Google Play updates by other apps, unless you know the issue has been fixed.
Note 1: Once it has been fixed, you can reactivate Google Play Store by searching it within Settings → Apps → All apps to continue to receive automatic updates again. Updates are usually a good idea. 
(“Ausnahmen bestätigen die Regel”)
Note 2: You probably want to let Google Play Services activated (along with its background data etc.), as afaik it handles things like push messages for some messengers and so on, things that you want to keep working. The one that actually updates (!) Google Play Services is the Google Play Store.
I got my phone working again last night thanks to @Pilo11. First I tried deactivating just background data of Play Store but it was not enough. This noon I have redone the procedure and deactivated Play Store completely and so far it’s working.
PS: One other complete alternative would be to just completely disable WiFi and mobile data - you decide what suits you better.