AD7

You should be able to add an alias for all users by updating the ProxyAddresses field. A bulk change can be made using the likes of ADSI Edit or Bulk AD (but just be careful, they're powerful tools). With regard to clashes / duplicate entries, DirSync will fail with exceptions - http://support.microsoft.com/kb/2647098

As James has mentioned, setting up the O365 tenancy is a relatively straightforward process. As a Microsoft partner, we can provide a few pointers in the first instance to help you register a trial and get you started. We're currently managing the migration of all schools in Nottingham on behalf of Nottinghamshire County Council, so we certainly know a thing or two about O365. Feel free to drop me a PM or for more info see @AD7consulting

The user's O365 login (username) can be amended by switching their UPN within AD. Likewise, the user's primary email address / aliases can also be modified from within the ProxyAddresses field.