How can I untheme a fieldset provided by theme_fieldset()?
You need to alter the form that contains that fieldset. You could do it using code similar to the following one.

function mymodule_form_alter(&amp;$form, &amp;$form_state, $form_id) {
  // Only alter user forms if there is more than one language.
  if (drupal_multilingual()) {
    // Display language selector when either creating a user on the admin
    // interface or editing a user account.
    if ($form_id == 'user_register_form' || ($form_id == 'user_profile_form' &amp;&amp; $form['#user_category'] == 'account')) {
      if (isset($form['locale'])) {
        foreach (element_children($form['locale']) as $id) {
          $form[$id] = $form['locale'][$id];
          $form[$id]['#access'] = $form['locale']['#access'];
        }
      }

      unset($form['locale']);
    }
  }
}



The code I wrote removes the fieldset from both the registration form, and the user profile form.
For the user registration form, the language fieldset is normally hidden to the users that don't have the permission to administer users. There could be a module that shows that fieldset to every user.
If you want to be sure that your code doesn't create problems to other modules, you should be sure it is executed after all the other modules that add fields to $form['locale'].
Usually there isn't any reason to remove a fieldset. It is convenient for the users to have related fields grouped together; in that way, if they don't need to edit them, they just collapse the fieldset. 


To be sure the code of your module is executed after all the other modules, you could do proceed with two methods:


You can alter the module weight, and increase it. In this way, the hooks implemented in your module would be executed for last.
You can implement hook_module_implements_alter() to alter the order some hooks are executed.

function mymodule_implements_alter(&amp;$implementations, $hook) {
  if ($hook == 'form_alter') {
    // Move mymodule_form_alter() to the end of the list. module_implements()
    // iterates through $implementations with a foreach loop which PHP iterates
    // in the order that the items were added, so to move an item to the end of
    // the array, we remove it and then add it.
    $group = $implementations['mymodule'];
    unset($implementations['mymodule']);
    $implementations['mymodule'] = $group;
  }
}


The documentation for hook_module_implements_alter() reports the following notes:


  Note that hooks invoked using drupal_alter() can have multiple variations (such as hook_form_alter() and hook_form_FORM_ID_alter()). drupal_alter() will call all such variants defined by a single module in turn. For the purposes of hook_module_implements_alter(), these variants are treated as a single hook. Thus, to ensure that your implementation ofhook_form_FORM_ID_alter() is called at the right time, you will have to have to change the order of hook_form_alter() implementation in hook_module_implements_alter().



Between the two methods, I would use the latter, as it doesn't change the order other hooks are executed, differently from the first.