I'm not sure if it's been tested in court, but there are certainly newspapers as you say that are doing this - including from quite major publishing houses. Personally I just open their pages in private browsing tabs anyway, if everyone did that it would probably kill the business model (even before we talk about uBlock).

My (non-lawyer) opinion is it's probably illegal if you're making a sham paid tier to justify working around the GDPR, and probably fine if you're a "real" paid product which offers the extra option of paying with data instead of cash. I guess in a court case it would be interesting what percentage of daily active users are on the paid tier.

Only kills the business model if they give you free reading articles.