Salesforce and WSSE security headers

I wanted to name this post as WSSE security header or How i lost my war with the webservice team much like this movie (If you have not watched this i would strongly recommend to watch it).

The requirement looked pretty straight forward consume wsdl , send the request and handle the response. But we faced the issue of WSSE headers. It looks something like this *********
The WSDL did not have the header part . So while sending request the above header was not present. The first approach we took was if it was possible for webservice team to support httpheaders instead of soap header. It was denied immediately.

The next step was to code the header into the generated apex class. It is bit tricky and involves extensive understanding of  WSDL2APEX functionality