Would assuming that the default language is English be valid? I know a large percentage of the Internet probably doesn't "know English", but if they can connect to the Internet, would they at least recognise enough words (like "language"") that they can choose a different language?
I think it could be anything making sense (the default for a german company could be german for instance) as long as switching away is smooth and discoverable. People not familiar with the english alphabet for instance could be lost in the site, getting overwhelmed by the unknow information, even if they know the word "english" or "language". For people like in that case, the page could be in french it wouldn't make much difference.
As a visual marker for language switching I imagined having a flag, but looking at the replies, that seems non optimal.
The best behavior could be a popup shown only to users who's accepted languages don't match the current language, and keep the choice in a cookie perhaps ?
What makes you think that? If their computer came with an OS preinstalled, with Mongolian, for example, as the language, they would not have to ever see any English anywhere. A flag might be more universally recognized way of selecting the right language.
The flag doesn't work for the billion people of India. We are massively multilingual; we have 22 official languages. Google.co.in is offered in 9 of those 22 languages -- each one with its own unique script, which are mutually un-intelligible. One Indian flag for all languages? No, thanks. Look at the confusion caused by the Metropolitan Police website [1].
If you can afford two pop-up lists, the approach of Lufthansa is the best [2]. If you want just one list, follow the installation screen of Ubuntu -- they write out the name of the language in its own script.