Cannot log in to google account when on data (works on Wifi)

Device: Lenovo A806 with Android 4.4.2

Problem: Cannot log in to google account while on data (works on wifi)

Description:
Cannot open google play (connection failed, retry) or add a new google account to the android settings (signing in, may take minutes). Also cannot eg log in to PokemonGO with google account while on data, but can log in with non-google account. The game keeps playing if later I go off-wifi. Wifi is required only for sign in. If I disconnect and allow some time to pass then cannot log in again on data.

Tried:

1. Date and time settings are automatic and I verified that the difference to atomic clock is under 1s.


2. Different SIM in different country has the same problem (network operator-independent)


3. Cannot add new google account (account independent, not related to 2-step verification or wrong password etc)


4. Hosts file contains only 127.0.0.1 localhost.


5. Uninstalling/Reinstalling, clearing cache, clearing data, forcing to stop the app and restarting does not seem to help because more than one app have the same problem.


6. Captured the HTTP/S traffic using Drony but didn't manage to understand which is the call to the google account, and see its status.

I know the question may seem a duplicate, but I haven't found any solved question about having this problem ONLY on data (wifi works so that rules out many solutions)