List entries without specific tag
You could try something like following reducing the tagged entries into IDs that you then filter against (see this thread):

{% set tag = craft.tags.search('All-Stars').first() %}
{% set allEntries = craft.entries.section('news') %}
{% set taggedEntries = craft.entries.section('news').relatedTo(tag).ids %}
{% set omitIds = 'and, not ' ~ taggedEntries|join(', not ') %}
{% set untaggedEntries = craft.entries.section('news').id(omitIds) %}