I spent the better part of today trying to figure this out so here is the brain dump. Basically I needed to do some prototyping that required a web service that used a custom UserNamePasswordValidator. Normally I have SSL setup in IIS and use credentials over a secured transport layer but I just wanted to whip up something simple for my prototype that would run in Cassini (Yes I know about IIS Express, haven't had time to try it out so it may have been a better route). Although WCF supposedly supports a new option to enable credentials over any transport, unsecured or not, it's the usual half baked Microsoft "feature" that doesn't really get you anywhere and wont generate the WSDL (I'm lazy and I didn't want to wire up the client config by hand). In any event you can just use message security and forgo the transport level security with this configuration:

  <system.serviceModel>
    <bindings>
      <wsHttpBinding>
        <binding name="UsernameAuthentication">
          <security mode="Message">
            <message clientCredentialType="UserName"/>
          </security>
        </binding>
      </wsHttpBinding> 
    </bindings>
    <services>
      <service name="WebServices.ContactService" behaviorConfiguration="UsernameAuthentication">
        <endpoint address="" binding="wsHttpBinding" bindingConfiguration="UsernameAuthentication" 
                  name="WebServices.ContactService" bindingNamespace="urn:Contacts" 
                  contract="WebServices.IContactService"/>
      </service>
    </services>
    <behaviors>
      <serviceBehaviors>
        <behavior name="UsernameAuthentication">
          <serviceMetadata httpGetEnabled="true"/>
          <serviceCredentials>
            <userNameAuthentication userNamePasswordValidationMode="Custom" 
                customUserNamePasswordValidatorType="WebServices.UserNamePasswordValidator, WebServices"/>
            <serviceCertificate storeName="My" storeLocation="LocalMachine" 
                x509FindType="FindBySubjectName" findValue="MyPrototype"/>
            <clientCertificate>
              <authentication certificateValidationMode="None" revocationMode="NoCheck" />
            </clientCertificate>
          </serviceCredentials>
        </behavior>
      </serviceBehaviors>
    </behaviors>
  </system.serviceModel>

Now the only other step is that you have to generate an X509 cert. I created a batch file to do this automatically (Requires the Windows/.NET SDK):

certutil.exe -delstore My MyPrototype

"C:\Program Files (x86)\Microsoft SDKs\Windows\v7.0A\Bin\makecert.exe" -sr LocalMachine -ss My -a sha1 -n CN=MyPrototype -sky exchange –pe

The last thing I needed was for the client not to try and validate the cert (As the CA cannot be validated):

[Test]
public void Contacts_Test()
{
    var contacts = new ContactServiceClient();
    contacts.ClientCredentials.ServiceCertificate.Authentication.CertificateValidationMode = X509CertificateValidationMode.None;
    contacts.ClientCredentials.UserName.UserName = "admin";
    contacts.ClientCredentials.UserName.Password = "admin";
    // ...
}

At this point everything works like a champeen!