How to list all untagged files in Mavericks Finder?
Ok, I should have taken a look at SuperUser, here's a way to do what AllInOne says without fiddling with XML files (and it's faster).
Simply create a new smart folder or hit cmd+F, choose "Raw Query" from the filters and type kMDItemUserTags != '*' in the field.