Classifier and Technique to use for large number of categories
This sounds like a pretty gnarly problem, so a lot of finesse will be needed to solve it.  @Jérémie Clos has some good points, but I wanted to add some more general thoughts...

With the size of your problem, you might want to think about a scalable framework like Mahout or H2O rather than scikit-learn, which is an awesome shared memory library, but does have scalability limitations.

With a categorical feature with cardinality of 5000 and 80 million training cases, a uniform distribution will only give you 16,000 training cases for each positive result.  However, the distribution probably isn't uniform.  I suggest that you eliminate the least common categories until you have thrown out 5% of the data and assess the cardinality of the remaining 95%.  This may give you a better clue about how to proceed i.e. what percent of the cardinality remains? 

Most multiclass classification algorithms are just lots of binary classifiers that are combined to produce a composite result, so will essentially do the work for you of splitting up the problem, binarizing the data (aka one-hot encoding), and training the classifiers, so you may not need to explicitly perform this splitting step.  Two exceptions to this, i.e. classifiers that can handle the multi-class problem intrinsically are decision trees and random forests (Mahout version). I would try both of these and hold them as benchmarks moving forward.

In terms of handling the addition of categories as data is added to the system, you will have to retrain sometimes.  This is sometimes referred to as the stability-plasticity dilemma.  The best way to handle this is probably only to make predictions on categories that comprise some threshold of the data and throw out the rest as outlier categories that are not powered well enough to predict on e.g. similar to the sanity check I suggest above.

Hope this helps!