Yeah, I hate that Debian is so wedded to Exim.... but any non-Exim package that doesn't have an alternate dependency that Postfix can satisfy is broken.

Sometimes apt-get seems to get unhappy about broken dependencies that will actually be fine once everything is configured, so it should work to let it remove the web server, then reinstall it. It's also likely that aptitude would be smarter than apt-get about that sort of thing (assuming you're not already using aptitude).

One of those multi-domain Postfix installs I mentioned was done on a Debian server that also had Apache installed (all from packages), so it is possible. I'd dig into it, but now all my machines are running Ubuntu.