What's a good classification algorithm for a large amount of classes?
I would suggest using Deep Learning and especially convolutional neural networks. This might be a generic approach to large scale classification tasks. One such example is identifying faces. As an example, 10.000 classes have been tackled by Sun et. al. in the following : http://ieeexplore.ieee.org/document/6909640/

And iterative learning is of course supported.