How so? The users just have to give their consent for it.

Because you can't have access to the service conditional on the consent.

So are we going to lose access to Google and most other services? Because they are effectively "pay with your data"

If gdpr had its way, then yes, you would probably lose access to google and pretty much the rest of the web. Right now, most companies are skirting around the law though so we will have to wait and see the real effects once the lawsuits start settling.