I am an undergraduate, and have recently come to terms with the fact that I may not have the intellect to do research in theoretical computer science, or be able to be admitted into and complete a PhD program. However, I would still like to be involved with theoretical computer science as I find it very interesting. So far, the only careers in theoretical computer science that do not require a PhD that I can think of would be being a secretary or administrative assistant for the theory group in some university. Are there any others?
I work at a national lab and in a directorate that employs many theoretical computer scientists, of which some do not have PhDs.
I think that what would differentiate or establish you would be a quality of your work. If you are a talented theoretician, strong at algorithms and you can/have been publishing your work in reputable theoretical computer science journals then I do not see why place like national lab would not hire you.
PhD is a testimony of ones ability to pursue relevant and significant research on his or her own.