Working on Bug 9735 [1] I ended up writing C4::Templates::getlanguagecookie and hooking C4::Auth::get_template_and_user in a way that the language can be changed using URL parameters, and the corresponding is properly set.
Using this new code, the language selection could be simplified by using JavaScript + document.location to generate the links to languages.