Try this:
1. create a node view
2. in 'Fields', add 'Node: nid'
3. in 'Relationships', add 'Taxonomy: Node'
4. in 'Filters', add 'Taxonomy: Vocabulary', in next step, choose 'Is empty (NULL)' as the operator.
5. test some of the nids given in the preview to see if they are the ones you are looking for, you might need to tweak a little the usage of relationship.
Step #3 is here to give you extra operators to choose from.
update
Okay the above assumes the content type only has one term field, so nevermind...
Now that I understand the issue better, I think you will probably need views_or module. Also we don't need 'relationship' anymore.
On my test Views, I use filter 'taxonomy:term(term id)' for each vocabulary, chain them together via Views_or. Set them to dropdown with hierarchy. Then highlight all terms in the vocab and check 'is none of' for the operator on the left. It's a very ugly query but that's the only way I got it to work...You'd better cache it for a better performance. I attached some screenshots hope to clarify the config part.