I have my doubts that WCF will work as you expect in this scenario. Where is MSMQ hosted? On the "server" or on the "client"? Or is there an independent MSMQ host? When disconnected, I believe the only system that will work is the one hosting MSMQ. The other system will fail to initialize WCF.
If your systems are on different domains, but the same AD forest, then you can use Domain Authentication transport security. If they are on forests entirely, then you must encrypt the payload yourself or rely on message-level security--i.e. certificates.
If the header is not sensative (i.e. the name of the function you are calling, who is invoking it, etc), then you can manually encrypt the payload. i.e. serialize your data to binary or xml, encrypt the serialized object, and then invoke your WCF method with the resulting byte-array as the argument.
You haven't explained why you want to avoid certificates. Clearly there's another constraint that you have not told us. Why not use certificates?