How does Whatsapp re-encrypt a message if they aren't supposed to have a key to decrypt? Is this done on the senders phone? Is it possible to re-encrypt within decrypting?
No, the WA server sends the changed public key of the recipient to the client, which has the unencrypted messages. Then the client reencrypts all pending messages and resends them.