Google apps losing connection to the servers when on mobile data
This turned out to actually be a network provider problem (in my case: SimpleMobile in the US) and the fix is incredibly simple: remove the proxy server from the APN and everything works.

The final hint I needed was the Google Now error message, googling that took me to this thread on xda-developers.

I have no explanation for why 'clear data' fixed the issue for a few minutes and why this didn't occur when tethering the tablet through the phone (maybe a cached server connection somehow?). It does however explain why the problem occured again when putting the SIM card into the tablet (the APN comes with the problematic proxy as a preset), and that should have tipped me off, I guess.