(Doing my bi-monthly perusal of Distutils activity, I find...)
.... Specifically, Greg Stien and Gordon McMillan (and plenty of people before them :-) seem to have what is considered "state of the art" in where this is heading.
[Jim Ahlstrom] I don't know of techniques which aren't Windows specific. Greg??Gordon??
Mark is referring to Greg's imputil.py (http://www.lyra.org/greg/small/) and some of the places I've taken it. My Win32-specific installer (ftp://ftp.python.org/pub/python/contrib/System/Installer_r_01.exe) makes use of this, but not all of it is Windows specific. (I originally packaged it so the cross-platform stuff was available separately, but there was no apparent interest from non-Windows users.)
Greg's imputil.py basically makes it possible to create a chain of importers, with the standard mechanism pushed to the end. Writing an importer is easy. You set up the chain is site.py.
I created a way of building archives of .pyc's (or .pyo's, though I've never worked with them). These are compressed with zlib. The standard library fits in about 500K and (subjectively) it is no slower and perhaps faster than the regular method. The mechanism handles modules and packages, and the building of an archive can be done in all kinds of ways (including using modulefinder from freeze).
I also created another kind of archive that can package up arbitrary stuff, and is fairly easily unpacked from C code.
All of the above is cross-platform.
On Windows, this means you can have a complete Python installation (independent of any other Python installation) in a single directory:
myPython/ python.exe (and/or pythonw.exe) python15.dll (completely vanilla) py_lib.pyz exceptions.py (from the std distr) site.py (hacked to load all the .pyz's) [any other .pyd's or .dll's you want] [more .pyz's if you want] [more .py's if you want]
(The Window's installation / standalone stuff goes further than this).
These .pyz's do work on Linux, but the steps Python goes through to determine where it lives is simpler on Windows. I'm not sure what it would take to get a single directory Python installation (independent of any other installed Pythons) working on *nix.