Sim é possível, você precisa de uma biblioteca que faça isto. Tem diversas opções dependendo da sua necessidade. Algumas opções (tem várias outras):
Para executar aplicações Python sem instalar o interpretador a solução mais interessante é a criação de um executável. Algumas opções:
- py2exe - Windows
- pyInstaller - Multi plataforma
- py2app - MacOS
Nem todos funcionam com a versão 3.
Conhece o Mercurial? Esta é uma aplicação criada com Python usando GUI sem precisar do interpretador.
Coloquei no GitHub para referência futura.