If you're wanting to avoid a loop, I think the best solution here would be to find the entries which do have a category set and work backwards using the |without()
filter. I can't see this being possible in only one query.
{# First, get your categories #}
{% set categories = craft.categories.group('optionalGroup').ids() %}
{# Find all news entries which have a category set #}
{% set newsWithCategories = craft.entries.section('news').relatedTo({targetElement: categories}).ids() %}
{# Now find news without categories #}
{% set newsWithoutCategories = craft.entries.section('news').ids()|without(newsWithCategories) %}
{# Finally retrieve the EntryModels #}
{% set newsEntries = craft.entries.section('news').id(newsWithoutCategories).find() %}
As you can see, there are quite a few calls to the DB being made here. This little algorithm would probably be more efficient with a loop.
{% set newsEntries = [] %}
{% for news in craft.entries.section('news').find() %}
{% if news.categories is empty %}
{% set newsEntries = newsEntries|merge([news]) %}
{% endif %}
{% endfor %}