It sounds like you want to migrate completely to O365 and have no on-prem server. B/C you are decommission your AD and Exchange server you wont' have domain accounts that your client machines will be attached to.
If this is the case you will not have a matched logon for windows 8.1. To logon with an Azure AD account (Azure AD is used for O365 account management) you need Windows 10 which does support this (and works well).
So if you want to keep Windows 8.1 - they will need to convert to local accounts or use Live accounts to "fake" the appearance of using the domain account. Essentially this means creating a live account with the email address of the current domain user. These however are not synced with O365. Either way they need new profiles on their machines so plan for that.
For O365 all plans support adding your custom domain so you can create users with username@mydomain.com logons. You need to own the domain, and it must be public, as you will have to make some DNS entries to validate ownership.
As to your MX question - you set the TTL low before you change it, so your window is small when you make the change. If you have something like a 24 hour TTL - it will take that long to propagate out the changes.
So- here is the approach I would take.
- Start a trail of O365
- Configure accounts using the default tenant names.
- Configure user accounts to use IMAP or POP to link their existing email accounts and evaluate that experience.
NOTE: Unless you plan on keeping this tenant DO NOT use your domain here. If the tenant expires it will tie up your domain and you will have great difficulty dealing with MS so you can use it on another tenant.
If you are ready to make the move - make sure you get the right plan. If you are don't need archiving or advanced discovery stay in the SMB plans. If you don't need one-drive or Lync, look at the Exchange Online only plans.
You don't need any 3rd party tools to do the migration - Follow the information here for a cut over migration
https://technet.microsoft.com/en-us/library/jj874016%28v=exchg.150%29.aspx
- Plan for the devices and applications they use. You will have to update Outlook clients and mobile devices to point to O365 (especially mobile - plan on removing and re-creating those profiles).
- Make sure you back up any Outlook rules and signatures they have.
- Review any transport rules you have in place and eventuate if they need to be added in O365
- Make sure can find your way around in the new ECP, and you understand how to trace mail messages, and create rules to bypass online protection, and read up on how to tweak EOP, a lot of things can only be configured with PowerShell ( https://technet.microsoft.com/en-us/library/jj723137%28v=exchg.150%29.aspx )
Hope that helps.