> That would make the existence of anonymous data practically speaking impossible to have on the web
For almost every type of data that is true. Transforming or substituting data doesn't make it anonymous; the patters in the data are still present. To produce actually anonymous data you have to do what the GDPR instructed: corrupt the data ("rendered anonymous") severely enough that the "data subject is ... no longer identifiable". You need to do something like aggregate the data into a small number of groups such that individual records no longer exist. Techniques like "differential privacy" let you control precisely how "anonymous" your data is by e.g. mixing in carefully crafted noise.
> 8192 bucket
While others have pointed out that this isn't actually limited to 13 bits of entropy for most people, there are at least two reasons that field is still very personally identifying. First, "x-client-data on its own" never happens. Google isn't wasting time and money implementing this feature to make an isolated database with a single column. At no point will the x-client-data value (or any other type of data they capture) ever sit in isolation. I used the IPv4 Source Address as an example because it will necessarily be present in the header of the packets that transport the x-client-data header over the internet. Suggesting that Google would ever use this value in isolation is almost insulting to Google; why would they waste their expensive developer time to create, capture, and manage data that is obviously useless?
However, lets say they did make and isolated system that only ever received 13 bit integers stripped of all other data. Surely that wouldn't be personally identifiable? If they store it with a locally generated high resolution timestamp they can re-associate the data with personal accounts by correlating the timestamps with their other timestamped databases (web server access logs, GA, recaptcha, etc).
> you'd need to describe a scheme such that, given an x-client-data header, and only an x-client-data header, you could identify one (and only one) unique person to whom that header corresponds
You should first describe why google would ever use that header and only that header. Even if they aren't currently using x-client-data as an identifier or as additional fingerprintable entropy, simply saving the data gives Google the option to use it as an identifier in the future.
[1] https://www.youtube.com/watch?v=pT19VwBAqKA https://en.wikipedia.org/wiki/Differential_privacy