Rebrand forcing email address change - what are my options?

At this stage your thinking is correct if using Exchange Online. You can do this relatively simply using Exchange on-premises. The only way I see it working is if you have all mail for newbrand.com going to one of the tenants, and that tenant contains all mailboxes for one organisation, while all users from the other organisation are represented as mailusers with a target address of the mailboxes in the other tenant. The problem with this is that you will need to use some sort of address re-writing appliance so that users in the tenant that does not contain newbrand.com have from/reply-to addresses of newbrand.com. Not an ideal scenario. I'd personally recommend slightly different SMTP addresses that might still give the idea that both organisations are part of the same entity.