There have been efforts to parallelize most of the well-known classifiers, including boosting [a paper], SVM [a paper], and even decision trees [a paper]. Of course, by admitting parallelism, you sometimes lose out on other aspects, whether it be algorithm implementability, sample complexity, or other usual suspects.
From the theory end, the question is harder because when you talk about learning you have to think about the target function. For example, we don't even know decision trees to be PAC-learnable, so if the target (as well as the method) is a decision tree, then we can't even learn it (yet) without introducing extra facets to the problem. Boosting gets around that by assuming a weak learning condition, SVM a margin, etc. I think those assumptions transfer to the parallel case to give you PAC learning.
But as always, there's a big gap between the frontiers (and thereby concerns) of theory and of practice. For example, in practice, it matters whether the parallelism is over cores or clusters. One algorithm developed especially for practical use in large-data settings is VW, and it's starting to support parallelism. You might be interested in the papers in the NIPS 2010 workshop on practical parallel learning.
