How do I approach a classification problem where one of the classes is defined by 'not any of the others'
I would use a two-step approach, using the idea of the $\hat{c_4}$ class you mentioned.

In the first step, use a binary classifier(trained on the whole dataset) to decide if a sample belongs to the class $\hat{c_4}$ (i.e. in any non-interesting class). For this, step you could also take a look in outlier detection methods, if the samples belonging in the "interesting" classes are much different than the rest.

If the result is negative, move on to the next step, a new classifier trained only on samples belonging in the classes $c_1,c_2,c_3$ and use that prediction as your final one.

I think that even using a simple clustering approach as a first step (e.g. 4-clustering k-means using as initial centroid values the average centroid $cent_j = \frac{\sum\limits_{x_i\in D: y_i=j}x_i}{\sum\limits_{x_i\in D: y_i=j}1}$  for each $c_1,c_2,c_3, \hat{c_4}$), would still be useful.