Appropriate algorithm for string (not document) classification?
You might find it useful to treat n-grams of characters as your feature space. Then you could represent a string as a bag of substrings.  With N = 4 or greater, you would capture things like ".com" in emails, "##.#" in dates, etc.

It might also help to encode all single digits as one reserved number-only-character.

An easy way to to this might be to create all the n-gram substrings for each string in your dataset, then simply treat that list of words as a document.  Then you could use term frequency or tf-idf vectors in your supervised step.

For example to create the substring uni-, bi-, and tri-grams for "whatever@gmail.com":

a = "whatever@gmail.com" 
b = set([a[x:x+y] for y in range(0,4) for x in range(0,len(a))]) 

set(['', 'co', 've', 'ai', 'eve', 'r@', 'at', '.co', 'gm', 'ev', 'tev', 'er', '@gm', 'ver', '@g', 'r@g', 'ail', 'il.', 'gma', '.', 'te', 'hat', '@', 'wha', 'om', 'wh', 'er@', 'mai', 'ma', 'ha', 'l.c', 'a', 'c', 'ate', 'e', 'g', 'i', 'h', '.c', 'm', 'l', 'o', 'l.', 'r', 't', 'w', 'v', 'com', 'il'])