Stratified bootstrap sampling is perfectly permissible to use. If you have the proportions of the class levels in the population I think you just make the class level a stratum and sample cases with each strata proportional to their representation in the population. Stratified bootstrap sampling amounts to sampling with replacement a specified number of times in each stratum.
Edit to the original answer: One aspect of the problem that was not addressed originally when the question was asked was a sensible way of reducing the number of predictors. The value of stratification is to reduce the overall variation. With so many predictors some may not be very useful anyway and hence the number of levels could possibly be reduced without hurting the value of the predictors for classification seriously. To emphasize what I said in the original answer since the bootstrap samples with replacement from each individual stratum no strata will be left out in any bootstrap sample. I think this addresses the recent comment by @kjetilbHalvorsen.