Setting up a proxy in AWS that adds a simple HTTP header to client requests

I would want to set up a simple proxy in Amazon Web Services that, in addition to acting as a proxy between the client and server, adds a simple (fixed) HTTP header to every client request before sending them to server.

I already looked at the most promising http://ift.tt/YnGjo7 which, however, doesn't seem to allow adding headers. The other but rather inconvenient option would be setting up a new EC2 (or BeansTalk) service to do the proxying work, but this feels like overkill for such a simple task, and additionally would need ELB/AutoScaling setup to ensure availability.

Is there any simple high-level way to get this done without falling back to setting up custom servers or services?