So my outgoing packets look like [Mac hdr][IP hdr][My header][Data]
Looks like what you are trying do is packet mangling. Check the netfilter/itpables pages (http://www.netfilter.org/documentation/index.html) for more info.
-- Pradeep Padala http://ppadala.blogspot.com -- Kernelnewbies: Help each other learn about the Linux kernel. Archive: http://mail.nl.linux.org/kernelnewbies/ FAQ: http://kernelnewbies.org/faq/