What about simply doing the split, keeping python-qt4 as a metapackage that installs everything for compatibility, and letting individual package maintainers progressively adjust dependencies ? A lintian warning to discourage packages to depend on the metapackage could then be introduce to speed up migration.