Which algorithm would be suitable for clustering a billion datapoints?
I don't know if there are other clustering methods which would work with this amount of data, but with K-means I would suggest this:

Run K-means with a varying number of instances picked randomly and study how much variation there is between the centroids depending on the data size (you can also study the variation across different random samples). I would expect the centroids to stabilize quite quickly with respect to data size: assuming the centroids become stable with data size N, there's no point running the full K-means process with more data.
Having obtained a model with N data points (the centroids), the model can be applied to all the remaining data points in order to find which cluster they belong to.

This is much more efficient than running the K-means process over the whole data since in the second stage the centroids are fixed, the algorithm doesn't have to iteratively update them.