The most important consideration is, until you see a problem, you probably don't need to worry about it. It's possible that your game will not fail on a single-threaded server until you start seeing hundreds of concurrent games, so I'd definitely write up some tests to simulate that situation before you try new approaches.
I second this. Threads aren't always all that helpful in languages like Python anyway. The
fastest Python web server right now is single-threaded.
Stackless Python is definitely something to look into, but I think you are best off sticking with Twisted for now. The whole point of that framework is to allow its users to efficiently and concurrently handle multiple connections without needing multiple threads. (It has pretty nice thread support anyway, if you end up needing that.)