What are the career prospects of doing a theoretical computer science PhD.?
If you truly have no country preference and are willing to go anywhere in the world, then there is a lot of potential opportunity.  In particular, I know there is a large amount of expansion in computer science in general (and thus likely theoretical as well) in the emerging universities of East and Southeast Asia, India, and the middle East.  Depending on your personal background and preferences, of course, you may find some cultural barriers to overcome.

I would also recommend considering the possibilities outside of traditional academia.  Theoretical computer science topics like you mention turn out to have a lot of applicability both in standard industry and in the in-between world of research institutes, national laboratories, startups, and non-traditional corporate environments that are not what people typically think of as "industry."

And then there's always just giving up academia altogether and making money, if your personal ethics would be OK with entering the financial world and playing hedge fund games...