Initializing PGP keys by one side I am using a PGP method to encrypt and decrypt messages shared between users A and B.

Upon the start of a message exchange is the initialization of the public and secret keys by both Users.

Lets say that User A downloads the message exhange app and he adds his friend (through phone number). He then wants to initialize a conversation. At this point User B has still not downloaded the app.

How are the keys to be safely generated if it is User A initializing the conversation? Technically, the request of creating the secret key for both parties would then have to be done by User A as well, which makes it not safe. 

Without the public key of User B (thus also the creation of the secret key for User B), User A will not be able to start sending encrypted messages.

The obvious solution is that he will need to wait before the friends accepts the friend request, thus creating and sharing the keys.

Is there a way to solve this issue without this restriction? That is, how can User A already start sending encrypted messages to User B, who has not signed up and accepted the request?
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.