When migrating Exchange server (for example from On-Premise Exchange to Office 365).
Is it possible to have the Exchange server sending an HTTP 451 (ActiveSync Redirect) to point Secure Mail to the new server without installing a new instance of Secure Mail?

Yes:
The HTTP 451 is the supported mechanism for changing the server information used by Secure Mail.
The HTTP 451 is allowed to contain a server path.

When Secure Mail receives a new path in a 451 redirect, the app respects that path in future requests.