All you need is for the two instances of the app to use separate sets of key pairs, where the keys have been generated on the device itself and the private keys never leave the devices, to share the private key for the conversation between the two devices. I don't know if Signal or any other app does this, but it's 100% conceptually possible.