Cannot add gmail account on iOS
I had this problem too.

When I checked on google if there was a security issue (https://myaccount.google.com/device-activity) I noticed that my iphone location was overseas.

I then realised that iPhone was connected to my company wifi and was routed via their overseas hub.

So I disabled the wifi so that only the local mobile data was being used. 

After that the add mail > google then worked.