Won't Python be too slow? The game
will be not trivial (like Tetris for
example), it may be needed to
calculate tasks for thousands of ships
in universe (though their AI can be
heavily simplified if those ships are
not seen to the player). Of course I
can write some critical parts in C,
but it will instantly complicate
building and deploying.
It's hard to say, but most of the time the limiting factor for performance is one's ability/experience as a developer, not the language. Note that EVE uses Stackless Python (see here and here for downloads of a related presentation). I don't recall the exact details, but apparently most of their server cluster is running Python. I would thus imagine that it could handle your scalability requirements, although prototyping to be sure would be good.
Windows users rarely have Python at
all (fortunately we have py2exe).
Python on Mac OS X can be outdated and
game may crash with obscure exception.
Wouldn't it be hard to deploy game in
Most users rarely have the appropriate binary dependencies for games, regardless of what technology those games were written in (even C requires a runtime component to be distributed). Deploying via py2exe or equivalent, or simply deploying the appropriate dependency, is something of a fact of life. While it's never the easiest thing (most installer technologies are painful), it's doable and shouldn't be a reason to eschew the language -- as I said, you'll likely need to handle something similar regardless.
Because of lack of libraries for
Python 3 I'll have to write game in
Python 2. Wouldn't transition to
Python 3 in couple of years be too
painful and time consuming?
This I don't know much about, never having really used Python 3. I don't expect Python 2.X will vanish any time soon, however, so I don't even suspect the lifetime of your game would be such that you'd need to transition over if you didn't want to, which makes this concern something of a non-issue.
As others have said, you're worrying too much about the language selection aspect of your project. Python is a powerful, useful tool for developing games and if you know it and like it you should develop with it. It doesn't matter how fast your game runs if it never gets finished because you worried too much about the language.