Assigning new items to existing similarity based clustering
I suggest you think about this in terms of "data set" and "training set" (technically, it is also recommended to have a separate test set). Once you have your clusters defined on the training set, your can start using them to classify any amount of new data without recalculating, by simply measuring similarity to cluster centroids, for example.

(This doesn't prevent you from deciding to enlarge your training set and data set later, just try to not do that selectively to avoiding overfitting.)