Malte,
Supporting alternative templates is straightforward with a small change to ad_return_template. Now this requires Tcl scripts that return a page to call ad_return_template. Once you do that, you can easily specify a alternative location for ADPs to support a different look. In general we want to step back first though, and clean up the pages so we can do better skinning through simple CSS changes.
Changing ADPs is a huge undertaking compared to editing a CSS file.