What is the database relationship between node_type and taxonomy_vocabulary tables?
Not to discourage database deep-diving, but if you're bootstrapped into the Drupal system with your system (i.e. programmatically creating nodes), then you don't have to necessarily understand how the DB works to get this working. Just use the functions in the node and taxonomy API to generate your array. 

Specifically, lets say you wanted to try for option #1. You could use 

node_type_get_types()

to pull a list of all of your content types, and then iterate through that to generate a list of taxonomy terms for each vocabulary. Here is a function I've used before to that effect, from VicTheme.com

/**
 * Helper function return all the taxonomy terms of a given node type
 * @param $type
 * The array of machine name of the content type that the function should look for taxonomy terms
 * the array format should be : array('machine_name');
 * @return
 *   An array of taxonomy terms containing tid =&gt; human name.
 */
function vt_commerce_api_get_vocabulary($type = array()) {
  // break if there are no types specified
  if (empty($type) || !is_array($type)) {
    return FALSE;
  }

  $output = array();
  foreach (field_info_fields() as $field) {
    if ($field['type'] == 'taxonomy_term_reference' &amp;&amp; is_array($field['bundles']['node'])) {
      foreach ($field['bundles']['node'] as $content_type) {
        if (in_array($content_type, $type)) {
          foreach ($field['settings']['allowed_values'] as $value) {
             $output[$value['vocabulary']] = $value['vocabulary'];
          }
        }
      }
    }
  }

  return $output;
}