I know this is an old question, but I ran into the same problem today, and solved it like this:
Select Id, ArticleNumber, Title from ArticleType__kav where Id not in (Select ParentId from ArticleType__DataCategorySelection) and PublishStatus = 'Online'
You should replace ArticleType__kav and ArticleType__DataCategorySelection based on the name of your Article Type.
For example, if you have an Article Type called "Answer", the query would look like this:
Select Id, ArticleNumber, Title from Answer__kav where Id not in (Select ParentId from Answer__DataCategorySelection) and PublishStatus = 'Online'
What it does is looks for articles where there is no record in the DataCategorySelection object for that article type. Only articles with a Data Category assigned will have a record in that object.