Here is a nice and laborious way to do it using SOAP::Lite - I copied the methods from this node from 2006. You need to work backwards up the tree calling the name/attr/value sequence on each node, and then combining them at the various levels. Have fun :)

use SOAP::Lite;
SOAP::Lite->import(+trace => 'all');

my $uri = 'urn:Foo';
my $proxy = 'http://localhost/';

my $client = SOAP::Lite
        ->readable(1)
        ->uri($uri)
        ->proxy($proxy);
 
$client->autotype(0);
 
my $security_token = 'MIIFazCCBFOgAwIBAg';
my $signature_value = 'E81kRkC92PFjxn5rr6';

my $BinarySecurityToken = SOAP::Header->name('wsse:BinarySecurityToken
+')
    ->attr({
        'EncodingType' => 'http://docs.oasis-open.org/etc',
        'ValueType' => 'http://docs.oasis-open.org/etc',
        'wsu:Id' => 'X509-38899A2DEAAE0A0A'
    })
    ->value($security_token);

my $CanonicalizationMethod = SOAP::Header->name('ds:CanonicalizationMe
+thod')
    ->value('Cmethod');

my $SignatureMethod = SOAP::Header->name('ds:SignatureMethod')
    ->value('SignatureMethod');

my $SignedInfo = SOAP::Header->name('ds:SignedInfo')
    ->value(\SOAP::Header->value($CanonicalizationMethod, $SignatureMe
+thod));

my $Signature = SOAP::Header->name('ds:Signature')
    ->value(\$SignedInfo);

my $SignatureValue = SOAP::Header->name('ds:SignatureValue')
    ->value($signature_value);

my $security = SOAP::Header->name('wsse:Security')
    ->attr({
        'xmlns:wsse' => 'http://docs.oasis-open.org/etc',
        'xmlns:wsu' => 'http://docs.oasis-open.org/etc'
    })
    ->value(\SOAP::Header->value($BinarySecurityToken,$Signature,$Sign
+atureValue) );
 
my $elem1 = SOAP::Data->name('ELEM1' => "value1");
my $elem2 = SOAP::Data->name('ELEM2' => "value2");

my $response = $client->mymethod( $security, $elem1, $elem2 );
[download]

 
Which gives me this output:
 

<soap:Envelope 
    soap:encodingStyle="http://schemas.xmlsoap.org/soap/encoding/" 
    xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/" 
    xmlns:soapenc="http://schemas.xmlsoap.org/soap/encoding/" 
    xmlns:xsd="http://www.w3.org/2001/XMLSchema" 
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
  <soap:Header>
    <wsse:Security xmlns:wsse="http://docs.oasis-open.org/etc" xmlns:w
+su="http://docs.oasis-open.org/etc">
      <wsse:BinarySecurityToken EncodingType="http://docs.oasis-open.o
+rg/etc" ValueType="http://docs.oasis-open.org/etc" wsu:Id="X509-38899
+A2DEAAE0A0A">MIIFazCCBFOgAwIBAg</wsse:BinarySecurityToken>

      <ds:Signature>
        <ds:SignedInfo>
          <ds:CanonicalizationMethod>Cmethod</ds:CanonicalizationMetho
+d>

          <ds:SignatureMethod>SignatureMethod</ds:SignatureMethod>
        </ds:SignedInfo>
      </ds:Signature>

      <ds:SignatureValue>E81kRkC92PFjxn5rr6</ds:SignatureValue>
    </wsse:Security>
  </soap:Header>

  <soap:Body>
    <mymethod xmlns="urn:Foo">
      <ELEM1>value1</ELEM1>

      <ELEM2>value2</ELEM2>
    </mymethod>
  </soap:Body>
</soap:Envelope>
[download]