How do I dynamically populate a select field?
I read somewhere that I couldn't use $form_state in a form hook


Not quite. If hook_form_alter() is being executed for the first time, then yes, $form_state can't be used to get a field's value because $form_state['values'] will not be set. 

However, if hook_form_alter() is being re-executed, like from an #ajax callback, then $form_state['values'] will be set with the current form values, just like it would be in #submit[] and #validate[] functions. By the way, the $form['#validate'][] functions are also executed during an #ajax callback. 

In your case, I believe you would get the current value of field_type from $form_state['values']['field_type'][LANGUAGE_NONE][0] (best to use the constant LANGUAGE_NONE instead of the string 'und'). Wherever you build the #options array for field_target_select during the execution of hook_form_alter(), you would do something like this:

$selected = 'some_default_value';
if (!empty($form_state['values']['field_type'][LANGUAGE_NONE][0])) {
  $selected = $form_state['values']['field_type'][LANGUAGE_NONE][0];
}
$child_options = my_function_to_get_child_options($selected);
$form['field_target_select'][LANGUAGE_NONE]['#options'] = $child_options;


What you have as your ajax callback function in your question looks correct:

function ajax_nudge_taxonomy_selected_callback($form, $form_state) {
  return $form['field_target_select'];
}