I thought I heard that py2exe was able to do this, but I never figured it out. Has anyone successfully done this? Can I see your setup.py file, and what command line options you used?
Basically I'm thinking of it giving me a single executable file that does something like unzips itself to maybe /temp and runs.
PyInstaller will create a single .exe file with no dependencies; use the --onefile option. It does this by packing all the needed shared libs into the executable, and unpacking them before it runs, just as you describe (EDIT: py2exe also has this feature, see minty's answer)
I use the version of PyInstaller from svn, since the latest release (1.3) is somewhat outdated. It's been working really well for an app which depends on PyQt, PyQwt, numpy, scipy and a few more.