It’s fairly simple, Deron; I think you’re just trying to absorb too much at once.
1) You need PHP to send the 404 header
2) You need to exit ExpressionEngine or it will still try to send its own headers, which will result in errors
3) Because you are exiting ExpressionEngine during the parsing of the parent template, you must keep all content on this single template.
4) You can use any tags you like in the template, except things parsed after PHP on Output. Without getting into the nitty gritty of parse order, that means that things like Weblog tags are fine. Template global variables and embed tags, however, are not.
So essentially, you just need to combine your templates that you use to build your 404 page into a single template (for this page only, I’m not suggesting you have to do that for the actual 404 template), and work from there. If it’s all too much trouble, that’s fine too; I’m just giving you options to do what you’re describing that you want to happen.