I'm unable to access this website. I can't let them use my data, GDPR is stopping me because compliance is apparently too expensive for this site. I don't have any option to click on a "I don't want any GDPR-provided 'rights'" button or e.g. sending such header with my requests.

AFAIK, the GDPR explicitly makes it illegal for a company to operate on a “pay with your data” basis. So no, they can’t.

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.