So I reached out to google engineers for support, turns outs you need to change the org policy "compute.vmExternalIpAccess". You need to enable it (default is disabled). After that the checkbox becomes available and my Colab notebook could access the internet. Problem was that it was very hard for me to locate which policy to change, so hope this helps people in the future