Create Your New Office 365 Tenant, and start verifying Your domain. Next step, login to the Office 365 tenant holding your domain, with a Global Administrator account.
But deleting the domain doesn’t work if any user still uses the domain for either SharePoint, Lync, Exchange or UserPrincipalName. This is also for deleted users that still remain in the graveyard, so these must be permanently deleted aswell.
Change all users to a different domain, perhaps the onmicrosoft.com domain.
This will change the login name, and after some time Email address and SIP address. SIP address usualy the last attribute to change, like it is the last to be created.
If any users have been deleted after using the domain we like to move, we also need to delete the graveyard.
Because Azure AD has a dumbster or deleted items backup for a grace period. But we need to use PowerShell with Azure AD Cmdlets and run these commands:
Start PowerShell With Administrator rights to run:
Set-ExecutionPolicy Unrestricted
Get-MsolUser –ReturnDeletedUsers | Remove-MsolUser –RemoveFromRecycleBin
Source: http://itiscloudy.com/?p=883
However if you wish to start fresh, you can create a new profile and do a data migration between two tenants. That will however, make users to re download all their old emails. If the internet bandwidth is a concern, I'd advise you to archive emails to a point where only the most recent emails are retained. Then do the migration, attach the Archive PST to refer old emails. Get help from this article for using Outlook for tenant to tenant migration of Office 365 mailboxes via PST export import.
If you want to remove a custom domain from a tenant and add it to another tenant, you can follow the detailed steps from the two articles below:
Remove a domain from Office 365
Add your users and domain to Office 365