SGDClassifier: Online Learning/partial_fit with a previously unknown label
It sounds like you don't want to start retraining the model every time a new label category appears. The easiest way to retain maximal information of past data would be train one classifier per category. 

This way you can continue to train each classifier incrementally ("online") with something like SGDClassifier without having to retrain them. 
Whenever a new category appears you add a new binary classifier for just that category. You then select the class with the highest probability/score among the set of classifiers.

This is also not much different from what you are doing today, because scikit's SDGClassifier already handles the multiclass-scenario by fitting multiple "One vs All" classifiers under the hood. 

If a lot of new categories keep coming up, of course, this approach might become a little tricky to manage.