How can I grant anonymous users access to the locale language select form without hacking core?
You should be able to just replace the #access property for the element added by the locale module in your form alter:

function MYMODULE_form_user_register_form_alter(&amp;$form, &amp;$form_state, $form_id) {
  // Use exactly the same access logic as the original, 
  // without checking for the 'administer users' permission
  $form['locale']['#access'] = ($form['#user_category'] == 'account' || ($form['#user_category'] == 'register'));
}


That's essentially the same as taking the &amp;&amp; user_access('administer users') part out of the core file.

All you need to make sure of is that your module hooks are run after those of the locale module (so the element actually exists when you try to alter it), which you can see how to do here.