Can the answer not just be to charge more for the ad-free tier? The gap between what I'm willing to pay for a streaming service with and without ads is a lot more than what the current going rate is.
The problem is that if you increase the price too much, the bad PR and hit to your reputation will likely offset any extra revenue. If a service like Hulu released a $50/mo ad-free tier people would freak out, even if they still had access to the same free ad-tier experience they do now. I don't know that it'd be beneficial.
This is boiling the frog though? These services were sold to us as something without ads. Seems really mob-like for the services to say to me: pay more or we're going to start showing ads on the thing we sold to you with the promise you wouldn't have any ads.
I don't think that's particularly a problem. Just because Netflix or Hulu offered one service when I first used them a decade ago doesn't mean they're obliged to provide the same service at the same price forever. I occasionally cancel a streaming service if I decide that it's no longer providing enough value to me, just like I'd cancel my current subscriptions if they started adding ads.