Having priorities and weight and language lists in the manifest help for negociation, but at the core of it, the user will want to choose language based on context and content.
> Language selection should be done on the client side, not on the server.
Yes.
Using a site specific list on the client side could also do it (let's say I always want Facebook in a language and Google in another, Linkedin in yet another etc.). It still will be pretty cumbersome, probably needs an auto-save and sync of the preferences, and still hits problematic cases, but it would be the most pragmatic solution.
The worst instance of it is IMHO the way Google Maps work, changing language based on the country gives the best display (local names in the proper writing, no internationalization), I wish there was an easier way than screwing with the Google account preferences. As you point out, having clients able to unambiguously request a specific version at each requests would gives us so many more options.