I think you are on the right track - but I've never done this myself so I'm very far from being an expert. You need to use mod_rewrite to send page requests through a Perl/PHP etc. script where you can add the header and echo the rest of the file.
There are several approaches - you can add the markup inline, but a user could use CSS absolute positioning to place something like a graphic which could cover your ads. You can frame the original page and place your ads in a separate frame to the top or the right. One thing to consider is that your script needs to do some sanity checking to ensure that it is not used to access content other than HTML pages or anything outside the document root.
You mention problems with PHP headers - as few of the free hosting providers offer support for server-side scripting for their end users, they are not faced with the same problem as you (ie. that the PHP scripts try to send HTTP headers which due to the prepended file come after some content has already been sent). Perhaps the framed-page approach would help in this case?