Fast k-means like algorithm for $10^{10}$ points?
k-means is based on averages.

It models clusters using means, and thus the improvement by adding more data is marginal. The error of the average estimation reduces with 1/sqrt(n); so adding more data pays off less and less...

Strategies for such large data always revolve around sampling:

If you want sublinear runtime, you have to do sampling!

In fact, Mini-Batch-Kmeans etc. do exactly this: repeatedly sample from the data set.

However, sampling (in particular unbiased sampling) isn't exactly free either... usually, you will have to read your data linearly to sample, because you don't get random access to individual records.

I'd go with MacQueen's algorithm. It's online; by default it does a single pass over your data (although it is popular to iterate this). It's not easy to distribute, but I guess you can afford to linearly read your data say 10 times from a SSD?