Are there pre-doc positions in TCS?
My answer only applies to Japan, I don't know about other countries. There is a special position termed "Research Student". I did that for 6 months before my masters .

I know that in general any student (foreigner or japanese) can do this. However, it is very common for foreigners to do this before starting the masters or phd program. It gives you adaptation time, and you also start studying the basics of your future research. Most student also start preparing for admissions.

During my time as a research student, I worked as a research assistant for my current advisor in different projects. I also took the time to really study quantum computing, which at that time I had 0 intuition for quantum mechanics. That was perfect for me, before doing any serious stuff.

EDIT:

Q: Are research student positions elusively research positions (i.e. no mandatory coursework)?

A: There is no mandatory coursework for research students. However, there are a lot of things you can do. In my case, I started directly doing research (mostly learning the basics), prepared myself for admissions, and colaborated in some projects. I also attended group seminars, school seminars, etc. You gain access to all activities in the university. You can also attend classes if you want, but that doesn't count for coursework in the graduate course. Another example is when you come from another university (from anywhere in the world) and you want to learn the tools of the trade in some field. So you talk with a professor, and if he agrees you can spend some time in his group as a research student.

Q: Also, are you expected to then stay for a Masters/PhD at the institute where you held the research student position?

A: No, you can change universities if you want. I have a friend that did exactly that. This is a position that doesn't give you a degree nor a diploma or anything, besides the experience.

It is very important also to note Okamoto-sensei's comment below. Specially, note that you don't get paid for doing this, unless 1) you have a good scholarship, like MEXT's scholarship; or 2) you get some funds from a company or a professor looking for phd students. 

To give you and idea, I post a couple of links explaining the requirements to be a research student. The first link is from my own university, and the second is from the university of Tokyo:

1) http://www.naist.jp/en/international_students/prospective_students/admission_information/research_student_applications/index.html

2) http://www.s.u-tokyo.ac.jp/en/admission/research-students.html

You can also find more information here

http://www.studyjapan.go.jp/en/index.html