Another option would be to update the user’s locale preference from their HTTP headers on login.
I think the best/simplest solution for doing this in a plugin is to ask the user to confirm their language preferences from the locale select input. If you are concerned that your users won’t be able to find that in their preferences, it could be added to the header for users who have not yet confirmed their language.