Microsoft posts setup articles for mobile devices. Just Google/Bing "Office 365 Mobile Configuration"
This link currently works (but if it doesn't use search): https://support.office.com/en-us/article/Video-Set-up-mobile-devices-with-Office-365-22ccc8e6-fa86-45ac-b83d-3e705a364845?ui=en-US&rs=en-US&ad=US
You can use Group Policy to script the Profile Change, or use a 3rd party tool. MessageOps has a little tool you can use called Config365 (http://www.config365.com/), it's run by an end user, but you could deploy that and have them just run it.
Edit
Config365 will use autodiscover to setup the client - so that has to be set to O365 before it will be useful. It's a local tool - you may be able to use HOST file to point it to Office 365.
For Group Policy - you can push out these registry keys via a batch file to setup a new default profile (you can use whatever method you prefer to assign these keys). It will add a new profile called "O365", then set it as default. When outlook starts it should attempt to configure the profile with the signed in user.
reg add HKCU\Software\Microsoft\Office\16.0\Outlook\Profiles\O365
reg add "HKCU\Software\Microsoft\Office\16.0\Outlook" /v DefaultProfile /t REG_SZ /d "O365" /F
This assumes Autodiscover is pointing to Office365, otherwise, you will just get setup to your Exchange server again. In a cutover - you are moving everyone at once so you should be prepared to update Autodiscover and Exchange SCP records when you do this. You will update the Exhcange end point with the Set-ClientAccessServer or Set-ClientAccessService -AutodiscoverInternalURL
command. An alternative is to use the Office group policy admin template and disable the SCP lookup for autodiscover.
An additional tool you can look at is SkyKick - it is not Free however.