Felicidade descobrir que python executava dentro de arquivo zip, como um tar no java. Ficou mais fácil fazer deploy de aplicações! O único ponto a considerar é que deve haver um arquivo __main__.py na raiz do zip que carrega o resto do projeto.
teste:

echo "print 'YEY'" > __main__.py && zip -9 teste.zip __main__.py && python test.zip

E para deixar o teste.zip executavel diretamente

(echo '#!/usr/bin/env python'; cat teste.zip) > teste && chmod +x test && ./teste

YEY