Large-scale string clustering
There are many possible approaches.  One approach that I would suggest investigating is finding all pairs of similar strings, and then applying a standard algorithm for clustering of sparse graphs.  There are multiple possible approaches for finding similar strings, depending on how you plan to measure similarity.

One approach is to measure similarity using the Levenshtein edit distance.  If you have $N$ strings, the naive way is to loop over all $N^2/2$ pairs, compute the edit distance for each, and save the pairs where the edit distance is below some threshold.  However, this doesn't scale when $N$ gets large.  Another alternative is to use fancier data structures and algorithms to find only the pairs of strings that are similar, e.g., BK-trees, ternary search trees, metric trees, Levenshtein automata, shingling, or other methods.  See, e.g., How fast can we identifiy almost-duplicates in a list of strings?, How to speed up process of finding duplicates/similar items in a large amount of strings?, Find all pairs of strings in a set with Levenshtein distance &lt; d, Efficient map data structure supporting approximate lookup, Efficient data structures for building a fast spell checker, and https://cstheory.stackexchange.com/q/4165/5038 for some references.  Credits to Pseudonym for part of this suggestion.

Alternatively, if you want to measure similarity using the number of characters the differ (i.e., like the edit distance but with only the "replace" operation and without the "insert" or "delete" operations), you could look at locality sensitive hashing as a way to find all pairs of similar strings.