To answer some of Double's questions, though probably not in a terribly useful way.
There are probably three types of headers
1) Those which were present in the original ROM/PCB/memory chips/CD/... Stuff like http://problemkaputt.de/gbatek.htm#gbacartridgeheader
basically. This might be a problem with some homebrew as companies stuck trademarked or copyrighted logos in there and required them to be present and homebrew authors opted out (the sega vs accolade court case having something to say about that but paranoia is not a bad thing when the only ones winning are the lawyers). These should never be removed, though there may be reasons for altering them.
2) Those which ROM dumpers made up to help things work -- if I just dump 5 ROM storage chips the emulator/flash cart will have no idea about how it is all arranged, and that is before we get onto extra hardware and custom setups that the ROM might need. The easiest way, especially if you are building a system with things still coming out, is to stick a header on the start of the ROM (or on the end as a footer, or some specified place...) and get everybody to agree to use it. The NES is a popular example but a variation on the theme has been seen as recently as the xbox 360 where unwriteable sections of consumer discs were faked and stored in other parts of the iso which the hacked firmwares played back as though they were "real". For the chips thing then the ROM/hardware does not care -- the extra hardware is there on the chip and you certainly don't care about emulators (or what's that in 1989?) or flash cart pirates.
3) Those which ROM dumpers/specific flash carts cooked up because they were incompetent or wanted some kind of vendor lock in. Seen as late as the early days of the DS (see golden sun team/GST dumps and neoflash if you are really bored, just don't ask anybody sorting release databases during that time) but some stuff exists for the NES and SNES. You might occasionally meet one that is technically 2) but using a format that failed to catch on, or was dreamt up by some emulator author, flash cart company, dumping collective or general fans of a device after the patch was made. Related to this would be things like interleaved ROMs and ROMs that opt for a different approach to endianness but it is usually a simple enough operation to convert between things.
There are a few extra annoyances that could crop up -- intros, additional compression (seen a few times on the DS for instance where some groups would compress the binaries using a legit tool but still compressed), alternative dumps (the PS1 era was also the era of 900 competing iso formats and everybody had their favourite, occasionally grudgingly moving to another when the need arose) and general modification (seen many times on the original xbox) but let us not go there right now.
Yes the classic patch method, such as IPS, is basically an overlay. Some newer types will have verification will rescan for the right offsets (close to what a patch itself will do), some older types have some basic logic (repeat this patch at these locations sort of thing) but the idea will still be the same. If you have a bunch of data offset from where the patch would be then you are going to struggle. If a header is just some extra data at the start then you likely can add the equivalent amount of data, patch, remove the equivalent amount of data and carry on with life.
In general if the nfo/release notes for the hack say it wants a header then if you have a headered ROM then great, otherwise there will probably be a tool built by someone that deals with ROM images for your chosen system. http://www.romhacking.net/utilities/
has most of them, or at least the good ones. As I mentioned the GBA earlier then without checking to see if they are there then http://www.no-intro.org/tools.htm
for fixing and basic manipulation and http://www.gameboy-advance.net/rom_tools/flash_advance_toolkit.htm
for the more advanced stuff/homebrew.