Hola:
Para hacer un ejecutable, como bien mencionas, puedes utilizar py2exe, realmente no compilas, pero coges aquella parte del interprete python que necesitas para que tu programa pueda instalarse y ejecutarse en cualquier máquina sin que tenga previamente que instalar el lenguaje.
Para usar py2exe, primero necesitas crear un archivo, que puede ser setup.py o el nombre que tu quieras, que contenga como mínimo:
from distutils.core import setup
import py2exe
setup(console=["nombre archivo"])
el nombre archivo ha de hacer referencia al path (ubicación) de tu programa python. Una vez hecho esto, lo guardas con el nombre que tu quieras, por ejemplo prueba.py. Ahora solo queda que ejecutes este pequeño escript que va a crear un EXE de tu programa python. Para ello, metete en el editor del sistema (MSDOS), entra en el directorio en el que se encuentra python instalado y ejecuta el script:
python prueba.py py2exe
cuando hagas esto, aparecerán un montón de mensajes avisando de la incorporación de librerías y demás, guardando tu ejecutable y todos los archivos en una carpeta que se llama dist (esta se crea en el interior del directorio python). Creo que esto es todo, no se si te he ayudado o ya lo has conseguido por ti mismo.
Salu2
Joaquín