Single pass / Streaming clustering

Check out scikit-learn's MiniBatchKMeans, which I've used to reasonably good effect in similar situations in the past:

http://scikit-learn.org/stable/modules/clustering.html#mini-batch-kmeans

http://scikit-learn.org/stable/modules/generated/sklearn.cluster.MiniBatchKMeans.html

In addition to the other suggestions, you may want to look into locally-sensitive hashing and random indexing, which can be done sequentially / online / out-of-core: http://en.wikipedia.org/wiki/Locality-sensitive_hashing

Such algorithms do exist, e.g. check out BIRCH :

BIRCH (balanced iterative reducing and clustering using hierarchies) is an unsupervised data mining algorithm used to perform hierarchical clustering over particularly large data-sets. An advantage of Birch is its ability to incrementally and dynamically cluster incoming, multi-dimensional metric data points in an attempt to produce the best quality clustering for a given set of resources (memory and time constraints). In most cases, Birch only requires a single scan of the database. In addition, Birch is recognized as the, "first clustering algorithm proposed in the database area to handle 'noise' (data points that are not part of the underlying pattern) effectively".

There are several implementations, e.g. this one in Java: JBIRCH. If you Google for "birch [your preferred language]", you'll find others.

There is a survey of data stream clustering just published on ACM Computing Survey (Oct 2013). Although not exactly what the OP asked, it may be never the less relevant for other readers interested in this question.

http://dx.doi.org/10.1145/2522968.2522981