how to save new value of autocomplete field with hook_form_submit?
As you said if you're unable to find the tid then its a new term. You can save the new term using taxonomy_term_save()

For example,

$term = new stdClass();
$term-&gt;vid = &lt;field city vid&gt;;
$term-&gt;name = $form_state['values']['first']['field_city'];
taxonomy_term_save($term);


After saving the new term you can access the tid like this,

$term-&gt;tid


If you want to fetch the vid referenced with particular field then look at the following thread - How to get the field settings in drupal 7