It seems the original author has found their solution, but for anyone else who gets here looking to add actual custom headers, if you have access to mod the generated Protocol code you can override GetWebRequest:

protected override System.Net.WebRequest GetWebRequest(Uri uri)
{
  System.Net.WebRequest request = base.GetWebRequest(uri);
  request.Headers.Add("myheader", "myheader_value");
  return request;
}

Make sure you remove the DebuggerStepThroughAttribute attribute if you want to step into it.

Tracking it down

At first I thought this was a coercion bug where null was getting coerced to "null" and a test of "null" == null was passing. It's not. I was close, but so very, very wrong. Sorry about that!

I've since done lots of fiddling on wonderfl.net and tracing through the code in mx.rpc.xml.*. At line 1795 of XMLEncoder (in the 3.5 source), in setValue, all of the XMLEncoding boils down to

currentChild.appendChild(xmlSpecialCharsFilter(Object(value)));

which is essentially the same as:

currentChild.appendChild("null");

This code, according to my original fiddle, returns an empty XML element. But why?

Cause

According to commenter Justin Mclean on bug report FLEX-33664, the following is the culprit (see last two tests in my fiddle which verify this):

var thisIsNotNull:XML = <root>null</root>;
if(thisIsNotNull == null){
    // always branches here, as (thisIsNotNull == null) strangely returns true
    // despite the fact that thisIsNotNull is a valid instance of type XML
}

When currentChild.appendChild is passed the string "null", it first converts it to a root XML element with text null, and then tests that element against the null literal. This is a weak equality test, so either the XML containing null is coerced to the null type, or the null type is coerced to a root xml element containing the string "null", and the test passes where it arguably should fail. One fix might be to always use strict equality tests when checking XML (or anything, really) for "nullness."

Solution

The only reasonable workaround I can think of, short of fixing this bug in every damn version of ActionScript, is to test fields for "null" and escape them as CDATA values.

CDATA values are the most appropriate way to mutate an entire text value that would otherwise cause encoding/decoding problems. Hex encoding, for instance, is meant for individual characters. CDATA values are preferred when you're escaping the entire text of an element. The biggest reason for this is that it maintains human readability.