I was thinking of doing something similar (not spreadsheets, but open editable pages). How to do generate the ids?
http://en.wikipedia.org/wiki/Base_36
If you don't care about the lengths of identifiers you can instead use a GUID. Otherwise you're down to compressed strings that slowly expand in length, and uniqueness tests on generation.