Initializing PGP keys by one side
You could use message specific keys, which encrypt the messages themselves. Once a secret key has been established you can encrypt the message specific keys with it and send them over in a new message (with meta-data) to user B. You should of course have some method of storing the encrypted messages somewhere for this to work.