Okay thanks for all the helpful comments. It turns out there is no way to do this using WP_QUERY alone.
The best way I can think of is to do it is like so:
$taxIds = get_terms($options['post-types'][$this->current_post_type->name], array(
'fields' => 'ids',
));
$uncategorisedQuery = new WP_Query( array(
'post_type' => $postType,
'posts_per_page' => -1,
'tax_query' => array (
array(
'taxonomy' => $taxonomyType,
'field' => 'term_id',
'terms' => $taxIds,
'operator' => 'NOT IN'
)
)
) );
Although @shanbp had a nice idea of creating a “Uncategorised” taxonomy and automatically applying it to each post on creation if no taxonomy is selected.