Basically, what you're saying here in your last paragraph is true. You'd give the subscribers of your WCF service the public key (.cer) file that they'd install and register within the LocalMachine/My store of their client machines.
On the host side, you'd install the cert public key in your LocalMachine/TrustedPeople store and the private key (.pfx or .pvk) in the host LocalMachine/Personal store.
You can vary the location of where you install/registry the public and private keys a bit, but then you'd have to configure your WCF service to find those cert elements on your server. The clients would have to do the same.
This does work. I've done it.
You can automate some of this using a .bat file and the makecert.exe and certmgr.exe DOS commands to ensure everything gets installed in the correct places.