Puedes usar PyInstaller, que es un programa gratuito que hace exactamente lo que quieres. Como dice el sitio web oficial :
PyInstaller es un programa que congela (empaqueta) los programas de Python en ejecutables independientes, bajo Windows, Linux, Mac OS X, FreeBSD, Solaris y AIX. Sus principales ventajas sobre herramientas similares son que PyInstaller trabaja con Python 2.7 y 3.3—3.5, genera ejecutables más pequeños gracias a la compresión transparente, es completamente multiplataforma y utiliza el soporte del sistema operativo para cargar las bibliotecas dinámicas, asegurando así la compatibilidad total.
También debo mencionar que puedes hacer un archivo ejecutable .py como cualquier otro archivo ejecutable de Linux (Unix), como este:
Este comando permite que se ejecute el archivo (vea esto )
user@linux~>chmod 0755 myProg.py
y luego ejecútalo así:
user@linux~>./myProg.py