There are plugins for both Firefox and Chrome (Modify Headers) that look like they would satisfy your needs. To support that using Selenium2Library, you could use an existing profile with those plugins instead of the clean temporary one you get otherwise.
Besides Browsermob-proxy there is also Fiddler.
I would push back if you can :) Selenium is for simulating real browser usage and end users do not set custom headers.
Kevin