Google could also block any facebook links from appearing as google search results if things become more tenuous. I highly doubt this would ever happen since they might face a heavy duty backlashing, but the thought is intriguing.
Google could also make an API requiring an API key to access it (for services/tools that depend on it). Refuse to give Facebook an API key, and allow apps that depend on the current method to transition. Within 30 days or so, shut down access to it via the predictable URL and make it some crazy URL when they request it.
You do know the referer header is optional don't you, I mean, you'd look pretty dumb relying on it for any web service because, you know, some crazy people turn them off altogether, perhaps with the Firefox add-on RefControl.