Exchange Online. Hybrid and non hybrid.

You have to wait for DirSync to replicate the changes to Exchange Online, which in most cases should take less than one hour. Now, if you absolutely must change the address directly in ExO for any reason, you can use the following workaround:

Set-Mailbox user -WindowsEmailAddress new@domain.com

The cmdlet above will change the primary SMTP address to new@domain.com, while preserving the old one as secondary, regardless of whether the user is synced or not. However, now the cloud and on-premises objects will be out of sync, and this change can potentially be overwritten by DirSync in the future. So this is more of a workaround, not a supported scenario.