I believe your question is equivalent to the question of solving the tragedy of the commons, which suggests it's indeed a tricky problem.
As a strawman proposal, we could take some of Elinor Ostrom's suggestions for a non-governmental solution (https://en.wikipedia.org/wiki/Tragedy_of_the_commons#Non-gov...) and apply them:
1. Introduce the concept of an API key to allow users to voluntarily segregate the traffic into accounts. API keys are only voluntary because it's easy to extract someone else's key from a client binary and masquerade as that person.
2. Issue API keys only to users who agree to a set of community standards.
3. Nontrivial usage that still complies with the community standards requires payment. The payment should be structured so that it's reasonable for medium-traffic users to stay, but more economical for heavy-traffic users to leave the community and start up their own clone of the service. For style points, the community standards should have specified that anyone who starts with the free community service and graduates to hosting a clone must also host low-traffic free users, basically causing the service to become federated. Maybe the original service replies with 301 redirects to the new service so that old clients keep working.
I think all of this can be fully automated, and if you're cool accepting Bitcoin for usage above the free tier, then you don't even have to worry about how to handle payments. There are plenty of VPS providers that accept Bitcoin these days, so the system is even closed-loop from the perspective of the service operator.