Get posts that DOESN'T have meta-keys?

Not sure what you mean by ‘set’, but what about:

$args=array(
  'meta_key' => 'your_custom_field',
  'meta_value' => 'your_custom_value',
  'meta_compare' => '!=",
  'post_type' => 'post',
  'post_status' => 'publish',
  'posts_per_page' => -1,
  'caller_get_posts'=> 1
);
$my_query = null;
$my_query = new WP_Query($args);

Note: wonder what happened to my first response to this thread?

I think you’d need two queries, one to fetch the post ids of posts with the given key, then a second query to pull posts, excluding the IDs passed in from the first query..

It won’t be an efficient query, but it would work.. (potentially large query if you have hundreds/thousands of records).

theindustry, how’s your PHP / MySQL skills? Considered writing a query to do it? Might work with a series of filters, but what’s this code for? Are you writing this code into a plugin/theme or is this more a case of trying to find redundant records?

Didn’t test this but, this queries all posts, and then loops through each post and if the custom field doesn’t exist display the post title:

<?php
$args=array(
  'post_type' => 'post',
  'post_status' => 'publish',
  'posts_per_page' => -1,
  'caller_get_posts'=> 1
);
$my_query = null;
$my_query = new WP_Query($args);
if( $my_query->have_posts() ) {
  while ($my_query->have_posts()) : $my_query->the_post();
    $custom = get_post_meta($my_query->post->ID, 'yourcustomfield', true);
    if ( ! $custom ){
    ?>
      <p><a href="<?php the_permalink() ?>" rel="bookmark" title="Permanent Link to <?php the_title_attribute(); ?>"><?php the_title(); ?></a></p>
      <?php
    }
  endwhile;
}
wp_reset_query();  // Restore global post data stomped by the_post().
?>

Depends on where you want to ‘see’ that displayed. See Template Hierarchy.