I want to write a C++ application with Qt, but build a prototype first using Python and then gradually replace the Python code with C++.
Is this the right approach, and what tools (bindings, binding generators, IDE) should I use?
Ideally, everything should be available in the Ubuntu repositories so I wouldn't have to worry about incompatible or old versions and have everything set up with a simple aptitude install.
Is there any comprehensive documentation about this process or do I have to learn every single component, and if yes, which ones?
Right now I have multiple choices to make:
Qt Creator, because of the nice auto completion and Qt integration.
Eclipse, as it offers support for both C++ and Python.
Eric (haven't used it yet)
Vim
PySide as it's working with CMake and Boost.Python, so theoretically it will make replacing python code easier.
PyQt as it's more widely used (more support) and is available as a Debian package.
Edit: As I will have to deploy the program to various computers, the C++-solution would require 1-5 files (the program and some library files if I'm linking it statically), using Python I'd have to build PyQt/PySide/SIP/whatever on every platform and explain how to install Python and everything else.
If you are just learning Qt and want to leverage the speed of prototyping that Python gives you, then I would recommend you make a sample project using PyQt.  As you said, there is a debian package, so you are just a simple apt-get away from making your first application.
I personally use gVim as my Python/Qt editor, but you can really use any Python-friendly editor without much trouble.  I liked WingIDE and they have auto-complete for Qt but once you sip from the vim kool-aid it's hard to switch.
I would say that PySide is 95%+ compatible with PyQt and the LPGL license is nice, but if you are just trying to prototype your first Qt app, then I don't think there is a real reason to use PySide.  Although, I do like the PySide docs better, you can also just use them and replace all the library references with PyQt.
Depending on the complexity of the application you are building, it might be better off to just start from scratch with a C++ version than to try to do a bunch SIP refactoring black magic.  Once you have a solid grasp of the Qt framework, you should be able to switch between the C++ and Python bindings pretty effortlessly.
Prototyping Qt/C++ in Python