How to add a select menu to a form with the ability to insert new values?
As a first step, You can use Select or Other module to collect values from user if not available...

Project page says


  Provides a new Forms API element which is a select/radios/checkboxes
  element that has an 'other' option. When 'other' is selected a
  textfield appears for the user to provide a custom value.


As a second step, You need to read this values on hook_node_presave and insert it into select list available options using code like below..

// Get the field info
$info = field_info_field('field_some_field');

// Get a reference to the values
$values = &amp;$info['settings']['allowed_values'];

// Manipulate the values in some way, e.g.
$values['new_value'] = 'New Value';

// Save the field
field_update_field($info);