What are some careers in theoretical computer science that do not require a PhD?
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.