You can apparently generate a private key that has to be combined with another one in order to work (I think this might be something to do with point multiplication), however, I don't know if that would work in the way you are wanting to (as I think the other involved party needs to have sent you a public key before you then generate the private key).

You can find this method in another thread (from memory etotheipi and/or JoelKatz discussed this) which at least is suitable for one person to generate a vanity address for another safely.