Sim é possível, você precisa de uma biblioteca que faça isto. Tem diversas opções dependendo da sua necessidade. Algumas opções:

- [PyQt][1]
- [PyGTK][2]
- [wxPython][3]

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][4] - Windows
- [pyInstaller][5] - Multi plataforma
- [py2app][6] - MacOS

Nem todos funcionam com a versão 3.

Conhece o [Mercurial][7]? Esta é uma aplicação criada com Python usando GUI sem precisar do interpretador.


  [1]: http://www.riverbankcomputing.co.uk/software/pyqt/intro
  [2]: http://www.pygtk.org/
  [3]: http://www.wxpython.org/
  [4]: http://www.py2exe.org/
  [5]: https://github.com/pyinstaller/pyinstaller
  [6]: http://undefined.org/python/py2app.html
  [7]: https://mercurial.selenic.com/