Usually when doing multi-class classification, we encode the classes using one-hot encoding. For example, in four-class classification, belonging to third class would be encoded as [0, 0, 1, 0]. In your case, you seem to have missing information in the data, since you know only something like "it's not class one, or two", i.e. [0, 0, ?, ?].
Simple solution could be to redefine the problem, and treat it as a multi-label classification problem, where for each training example you would code as 0's the classes that are not positive, while positive, or unknown classes are coded as 1's.
[0, 0, ?, ?] -> [0, 0, 1, 1]
[1, 0, 0, 0] -> [1, 0, 0, 0]
[?, ?, 0, ?] -> [1, 1, 0, 1]
This would make your algorithm learn to classify the possible positives, so you could choose among them to make proper classification.
Notice, that this makes it a noisy labels problem. You have data, but imprecise. Imagine that you had three, very similar, examples, and you would know that the first is "not class one", second is "not class one, or four", while third is "not class three, or four". From this, you could deduce that the examples are certainly not from class four, and probably not from class one, or two, so they likely come from class two. This is how, given enough data, your algorithm could learn the correct answer given noisy labels.
If you additionally have a subset of good data, where all the examples have proper labels, than you could use this data to learn a standard multi-class classifier. Next, you could combine both results, so that first classifier is used to filter the likely classes, and second to make the classification. For example, if the first classifier returns the probabilities of being non-negative $(p_1, p_2, p_3, p_4)$, and the second one probabilities of belonging to the class $(q_1, q_2, q_3, q_4)$, than you could combine those to make classification by taking
$$
\operatorname{arg\max}_i\; (p_1 q_1,\, p_2 q_2,\, p_3 q_3,\, p_4 q_4)
$$
