How can I handle missing categorical data that has significance?
Imputation and dealing with missing data a broad subject; you should start by researching standard material on this subject.

The first question to figure out is Why is some data missing?  and What is the process that causes data to be missing?  It's important to understand how this happens, because this will affect what solution is appropriate.

Randomly missing data

If data is missing totally at random (whether a value is missing does not depend on any of the feature values of that item), then imputation can be appropriate.  It should not create bias, if you do it appropriately.  There are many techniques for imputation.  You don't mention what you tried or why you think it will bias your results, but in general, if you use an appropriate method of imputation, there is no reason why it needs to bias your data.

Alternatively, you can use a classifier that can tolerate missing data.  Some classifiers are designed to handle missing data and can tolerate it.  However, I don't know of any reason to use them over imputation.

Non-randomly missing data

In contrast, if the chance for data to go missing for some object depends on the value of the features of that object, then you have a bigger problem.  In that case imputation can create bias -- as can any other method.  Your best hope is to understand in greater depth the random process that causes data to be missing and the probability distribution (probability that data goes missing, as a function of feature values), and try to design a procedure that is appropriate for that process.

Your specific situation: all features missing

Your specific situation is especially weird: it appears in your case either all features are missing, or none are.  That's a weird one.  For instances where the features are missing, you have absolutely no information about those instances.  So, the best classification decision in that case is probably a very simple rule: take whichever class appears most frequently in your training set (or, most frequently among instances with missing data).  Run the classifier on the remaining instances, i.e., the instances with no missing data.

But in real life this situation is pretty rare.  It's more typical that some features are missing and others are present, and that requires more work to handle.