One is allowed to speak Lashon Hora about a non-Jew. The Pasuk says "לֹא-תֵלֵךְ רָכִיל בְּעַמֶּיךָ" - "Thou shalt not go up and down as a talebearer among thy people" (Leviticus 19:16). The words "among thy people" teach you that one is only forbidden to speak Lashon Hora about those who are included within "thy people". This goes so far as to include a Jew who has removed himself from the category of amongst his people (by committing certain sins that classify him as a wicked person; what those sins are is a whole different discussion). This limitation of "עַמֶּיךָ" also excludes non-Jews form the prohibition of Lashon Hora, as they are not included in עַמֶּיךָ.
Of course, as you mentioned in your question and other comments, there might be other considerations with regards to speaking 'Lashon Hora' (note: to simplify things, when I write Lashon Hora in quotations, I'm referring to words that would be considered Lashon Hora if they were said to/about a Jew). You brought up Chillul Hashem, which has it's own separate Halachos as to what it is. If what one says is a Chillul Hashem, it is of course forbidden, even though it might not be a sin of Lashon Hora.
Another reason to avoid speaking 'Lashon Hora' about non-Jews is because it creates a bad habit. We humans are creatures of habit, and if we get in the habit of speaking 'Lashon Hora' when it is permitted, we might accidentally start speaking Lashon Hora when it is forbidden.
This does have a few important practical applications. For example, if your Jewish coworkers are badmouthing your Jewish boss (even without you joining in, just listening), you might have an obligation to protest the Lashon Hora in some manner. If he were non-Jewish, you would likely not need to make a protest over the 'Lashon Hora' (as there is no prohibition of Loshon Hara). (You may need to protest due to other factors such as Chillul Hashem depending on the situation, but this answer is just focusing on the Loshon Hara aspect.)