After some investigation it turned out to be a bug in the server-side framework Yii, which does not properly sort preferred languages when they are mentioned in the Accept-Language
header with the same priority. For example, if two languages are given with omitted weightes (meaning 1.0 by default), there is no guarantee that Yii will choose the first one. In my case it took the second. Unfortunately, the fix of the bug was eventually eliminated from the trunk.
As for Android, it seems always passing the http header according to current user language chosen in the system settings. It's ok for most of use cases, so there is no need to (try to) override the header.