Is there a query string for edit.php to show all posts that have no custom taxonomy terms?

Use a tax_query with a NOT IN operator.

$args = array(
  'post_type' => 'post',
  'tax_query' => array(
    array(
      'taxonomy' => 'sms_premium_posts',
      'field' => 'slug',
      'terms' => 'Premium',
      'operator' => 'NOT IN'
    )
  )
);
$query = new WP_Query( $args );

Now, to make that work on the post edit page via a $_GET string something like what you have in your question, you could do this:

function alter_edit_php_query_wpse_100794($qry) {
  if(isset($_GET['notin'])) {
    $qry->set(
      'tax_query',
      array(
        array(
          'taxonomy' => 'category',
          'field' => 'slug',
          'terms' => sanitize_title_with_dashes($_GET['notin']),
          'operator' => 'NOT IN'
        )
      )
    );
  }
}
add_action('pre_get_posts','alter_edit_php_query_wpse_100794');

That is very rough. You probably want more conditionals, such as is_admin, to prevent that from working globally.

Reference

http://codex.wordpress.org/Class_Reference/WP_Query#Taxonomy_Parameters