Algorithms for text clustering

Check the Stanford NLP Group's open source software, in particular, Stanford Classifier. The software is written in Java, which will likely delight you, but also has bindings for some other languages. Note, the licensing - if you plan to use their code in commercial products, you have to acquire commercial license.

Another interesting set of open source libraries, IMHO suitable for this task and much more, is parallel framework for machine learning GraphLab, which includes clustering library, implementing various clustering algorithms. It is especially suitable for very large volume of data (like you have), as it implements MapReduce model and, thus, supports multicore and multiprocessor parallel processing.

You most likely are aware of the following, but I will mention it just in case. Natural Language Toolkit (NLTK) for Python contains modules for clustering/classifying/categorizing text. Check the relevant chapter in the NLTK Book.

UPDATE:

Speaking of algorithms, it seems that you've tried most of the ones from scikit-learn, such as illustrated in this topic extraction example. However, you may find useful other libraries, which implement a wide variety of clustering algorithms, including Non-Negative Matrix Factorization (NMF). One of such libraries is Python Matrix Factorization (PyMF). Another, even more interesting, library, also Python-based, is NIMFA, which implements various NMF algorithms. Here's a research paper, describing NIMFA. Here's an example from its documentation, which presents the solution for very similar text processing problem of topic clustering.