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):

- [PyQt][1]
- [PyGTK][2]
- [wxPython][3]
- [kivy][4]
- [TkInter][5]

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

Nem todos funcionam com a versão 3.

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

[Coloquei no **GitHub** para referência futura][10].


  [1]: http://www.riverbankcomputing.co.uk/software/pyqt/intro
  [2]: http://www.pygtk.org/
  [3]: http://www.wxpython.org/
  [4]: https://kivy.org/#home
  [5]: https://wiki.python.org/moin/TkInter
  [6]: http://www.py2exe.org/
  [7]: https://github.com/pyinstaller/pyinstaller
  [8]: http://undefined.org/python/py2app.html
  [9]: https://mercurial.selenic.com/
  [10]: https://github.com/maniero/SOpt/blob/master/Python/Conceptual.md