[SalesForce] Forming SOAP header through apex class if the WSDL provided has no information regarding the header

You will need to correctly set the SessionHeader on the instance of CaseCreationUtility.CS_CaseCreationUtility. You don't need to set the session id in the inputHttpHeaders_x map.

E.g.

CaseCreationUtility.CS_CaseCreationUtility stub = new CaseCreationUtility.CS_CaseCreationUtility();
ts.SessionHeader = new CaseCreationUtility.SessionHeader_element();
ts.SessionHeader.sessionId = oauth.access_token;

You may also need to adjust the endpoint URL if it differs from the Org that it was generated from.

// You will need to set the instance (here na5) 
// to match the origin of the sessionId
ts.endpoint_x = 'https://na5.salesforce.com/services/Soap/class/OptionalNamespaceHere/CaseCreationUtility';

The requested oAuth session id should have the full or api scopes to be able to access the web service. The session should be to the same org where the Apex web service is implemented.

If it doesn't work initially with the oAuth derived session, try getting the web session id from the sid cookie or via anonymous Apex with UserInfo.getSessionId().

You can generate SOAP headers for use with WebServiceCallout.invoke using a member and a corresponding string with the _hns suffix.

For reference, Wsdl2Apex processes this around Line 86 of the BindingClass.java file.

You will need to create an inner class to contain the header data.

Here is an example from the UPS XAV Service WSDL. The code was generated using the FuseIT SFDC Explorer Wsdl2Apex function (Disclosure, this is my current employer).

// Generated by FuseIT WSDL2Apex (http://www.fuseit.com/Solutions/SFDC-Explorer/Help-WSDL-Parser.aspx)
// Methods Included: ProcessXAV
// Primary Port Class Name: XAVPort 
public class wwwUpsComWsdlXoltwsXavV10 {
    public class XAVPort {
        public String endpoint_x = 'https://wwwcie.ups.com/webservices/XAV';
        public Map<String,String> inputHttpHeaders_x;
        public Map<String,String> outputHttpHeaders_x;
        public String clientCertName_x;
        public String clientCert_x;
        public String clientCertPasswd_x;
        public Integer timeout_x;

        // Setting this member will populate the <env:Header/> element 
        public wwwUpsComXmlschemaXoltwsUpssV10.UPSSecurity_element UPSSecurity;
        private String UPSSecurity_hns = 'UPSSecurity=http://www.ups.com/XMLSchema/XOLTWS/UPSS/v1.0';

        private String[] ns_map_type_info = new String[]{'http://www.ups.com/XMLSchema/XOLTWS/UPSS/v1.0','wwwUpsComXmlschemaXoltwsUpssV10','http://www.ups.com/XMLSchema/XOLTWS/Common/v1.0','wwwUpsComXmlschemaXoltwsCommonV10','http://www.ups.com/XMLSchema/XOLTWS/Error/v1.1','wwwUpsComXmlschemaXoltwsErrorV11','http://www.ups.com/XMLSchema/XOLTWS/xav/v1.0','wwwUpsComXmlschemaXoltwsXavV10'};

        public wwwUpsComXmlschemaXoltwsXavV10.XAVResponse_element ProcessXAV(wwwUpsComXmlschemaXoltwsCommonV10.RequestType Request,String RegionalRequestIndicator,String MaximumCandidateListSize,wwwUpsComXmlschemaXoltwsXavV10.AddressKeyFormatType AddressKeyFormat) {
            // ...
        }
    }
}

public class wwwUpsComXmlschemaXoltwsUpssV10 {
    public class UPSSecurity_element {
        public wwwUpsComXmlschemaXoltwsUpssV10.UPSSecurity_UsernameToken_element UsernameToken;
        public wwwUpsComXmlschemaXoltwsUpssV10.UPSSecurity_ServiceAccessToken_element ServiceAccessToken;
        private String[] UsernameToken_type_info = new String[]{'UsernameToken','http://www.ups.com/XMLSchema/XOLTWS/UPSS/v1.0','','1','1','false'};
        private String[] ServiceAccessToken_type_info = new String[]{'ServiceAccessToken','http://www.ups.com/XMLSchema/XOLTWS/UPSS/v1.0','','1','1','false'};
        private String[] apex_schema_type_info = new String[]{'http://www.ups.com/XMLSchema/XOLTWS/UPSS/v1.0','true','false'};
        private String[] field_order_type_info = new String[]{'UsernameToken','ServiceAccessToken'};
    }
    public class UPSSecurity_ServiceAccessToken_element {
        public String AccessLicenseNumber;
        private String[] AccessLicenseNumber_type_info = new String[]{'AccessLicenseNumber','http://www.ups.com/XMLSchema/XOLTWS/UPSS/v1.0','string','1','1','false'};
        private String[] apex_schema_type_info = new String[]{'http://www.ups.com/XMLSchema/XOLTWS/UPSS/v1.0','true','false'};
        private String[] field_order_type_info = new String[]{'AccessLicenseNumber'};
    }
    public class UPSSecurity_UsernameToken_element {
        public String Username;
        public String Password;
        private String[] Username_type_info = new String[]{'Username','http://www.ups.com/XMLSchema/XOLTWS/UPSS/v1.0','string','1','1','false'};
        private String[] Password_type_info = new String[]{'Password','http://www.ups.com/XMLSchema/XOLTWS/UPSS/v1.0','string','1','1','false'};
        private String[] apex_schema_type_info = new String[]{'http://www.ups.com/XMLSchema/XOLTWS/UPSS/v1.0','true','false'};
        private String[] field_order_type_info = new String[]{'Username','Password'};
    }
}

If you do want to go down the HttpRequest path as Keith commented, the FuseIT SFDC Explorer tool can also generate code using the HttpRequest. I cover this in my Dreamforce 2014 presentation.