How to move a form field inside a container
The fieldset is added by the theme_date_combo() function, which is on the element itself, not the wrapper (i.e. $form['field_birthday']). 

To get this to work you'll need to temporarily move the Show Birthday field into the date_combo field, like so:

function MYMODULE_form_article_node_form_alter(&amp;$form, &amp;$form_state, $form_id) {
  $form['field_birthday'][LANGUAGE_NONE][0]['field_show_birthday'] = $form['field_show_birthday'];
  unset($form['field_show_birthday']);

  $form['#validate'][] = 'MYMODULE_article_node_form_validate';
}


Importantly, you'll also need to move that field back to where it originally was when the node form is validated. You won't get any errors if you don't, but the field_birthday value simply won't be saved.

function MYMODULE_article_node_form_validate(&amp;$form, &amp;$form_state) {
  $form_state['values']['field_show_birthday'] = $form_state['values']['field_birthday'][LANGUAGE_NONE][0]['field_show_birthday'];
  unset($form_state['values']['field_birthday'][LANGUAGE_NONE][0]['field_show_birthday']);
}


The above assumes you're making changes to the Article node form, just replace article with the name of your content type in the code. If your fields are inside another fieldset you might need to dig a bit further into the form array to find out how to access the precise field, but the logic will remain the same.

This is the result I get with that code (using admin theme):



I've tested both add and edit node forms and they seem to work perfectly using this method.