How to query the WordPress database to get posts of a certain custom post type, taxonomy and field?

I would use a custom query like this:

$amsterdamstore_args = array(
  'post_type' => 'store',    // This is your custom post type
  'tax_query' => array(
    array(
      'taxonomy' => 'city',    // This is your custom taxonomy
      'terms' => 'Amsterdam',    // The term you search for
      'field' => 'name',    // Check against the term's name (you might use 'slug', too)
    )
  ),
  'meta_query' => array(
      'relation' => 'AND',    // you could use OR, too - depending on what you want
      array(
          'key' => 'store_postal_code',    // Here goes your post_meta field's key
          'value' => '1234AB',    // Here goes your post_meta field's value
          'compare' => '=',
      ),
      array(
          'key' => 'store_parking',    // Here goes your post_meta field's key
          'value' => 'SOME_VALUE',    // Here goes your post_meta field's value
          'compare' => '=',
      ),
  )
);

These are the arguments you need for WP_Query or – if that is of more use to you – get_posts. – Loop through the results, get_post_meta as you wold do normally and there you go.

BTW: You can combine the meta_query arrays to your liking: Add some, leave some, and you could even nest deeper and do something like AND ( A OR B ) ( C OR D )…