Exclude from the query posts with meta_key and meta_value

I think you’ll need to add a posts_join filter, to join the posts and postmeta tables.

This link should be helpful: http://codex.wordpress.org/Custom_Queries, in particular this piece of example code:

add_filter('posts_join', 'geotag_search_join' );
add_filter('posts_where', 'geotag_search_where' );

function geotag_search_join( $join )
{
  global $geotag_table, $wpdb;

  if( is_search() ) {
    $join .= " LEFT JOIN $geotag_table ON " . 
       $wpdb->posts . ".ID = " . $geotag_table . 
       ".geotag_post_id ";
  }

  return $join;
}

function geotag_search_where( $where )
{
  if( is_search() ) {
    $where = preg_replace(
       "/\(\s*post_title\s+LIKE\s*(\'[^\']+\')\s*\)/",
       "(post_title LIKE $1) OR (geotag_city LIKE $1) OR (geotag_state LIKE $1) OR (geotag_country LIKE $1)", $where );
   }

  return $where;
}