txid is just some kind of hash of the transaction itself. Slightly change the tx and you get a different txid.

The end of the OP_RETURN has a random hexadecimal string. Randomize that, sign & finalize the tx, check the resulting txid. If no match, generate a new random hex string and repeat...