How can I create a View that shows nodes without a relation? On my site, all the nodes of content type ABC are supposed to have a relation (from the Relation module) to a user. 

However, although the relations are usually created in Rules, somehow this didn't happen for some nodes, and to make it worse, it happened randomly (non-sequentially).

So, I would like to make a view that shows the nodes which do not have any relation-- but I can't figure out how to configure the view to do that.

If I add a Relationship of Has relation Node -> User, I can get all the nodes that DO have a relation, but how do I get all the nodes that DO NOT have a relation?
You can just create a new filter criteria using your user reference field, and choose "Is empty (NULL)" as operator.

That will show all nodes that don't have any value in the user reference field.