<p>How can I distribute a standalone Python application in Linux?</p>

<p>I think I can take for granted the presence of a recent Python interpreter in any modern distribution. The problem is dealing with those libraries that do not belong to the standard library, i.e. wxPython, scipy, python cryptographic toolkit, reportlab, and so on.</p>

<p>Is there a working Linux counterpart to, say, py2exe (which, by the way, I have never tried)?
Is there a free, opensource one?</p>

Nope.
Python is notoriously flaky with respect to different setups. The only sane way to deploy a python app is to ship the whole bundle of interpreter and libraries that you are relying on with your code. That will most likely work.
Update 2019: I stand by this. Virtualenv is a way of packaging libraries and interpreters together. Tox is a testing tool to test that interpreter/dependency matrix. Docker is a widely used way of then deploying the bundle.