Video. One byte per frame. 25 bytes/sec is enough for simple messages, and given how noisy video is, it's likely undetectable if it's buried in a pattern of +/-1 RGB offsets.

You don't even need the original. You just need to agree a PNRG seed, a PNRG algorithm, and the algorithm you'll be using to work out xy and RGB offsets.