Classifier for large number of labels
For multiclass classification problems there are multiple algorithms which are inherently built in a way to be able to solve them.
Some examples: kNN, naive bayes, decision trees...

For the performance to be accurate on all labels and for the classifier to show little bias, you can use other approaches: you can oversample minority classes or undersample majority classes, in a way that all the labels have the same number of points associated with them.

Here you can find some interesting answers about how to fight against class imbalances on decision tree classification: https://stats.stackexchange.com/questions/28029/training-a-decision-tree-against-unbalanced-data