PyInstaller를 사용하면 특별한 의존성 없이 --onefile 옵션을 이용하여 .exe 파일을 생성할 수 있습니다. PyInstaller는 필요한 라이브러리를 하나의 실행파일에 묶어놓고, 실행파일이 실행하기 전에 묶어놓은 라이브러리들을 해제하여 실행되는, 질문하신 분께서 생각하시는 그대로의 방식으로 작동합니다. (py2exe 또한 이러한 기능을 갖추고 있네요. minty의 답변을 참고하세요.)

저는 PyInstaller의 최신 릴리즈(1.3)가 구식인 관계로 svn에 올라온 버전을 받아 사용하고 있습니다. PyQt, PyQwt, numpy, scipy 등에 의존하는 앱들에도 굉장히 잘 작동합니다.