There are a lot of articles out there discussing cross-site collection navigation and how to implement it. The first thing I would ask is how is this navigation managed? If the navigation is generated automatically then it would be simple to create a web part that queries all site collections and then displays the site structure. However, if you are expecting users to manually manage this navigation then you will need to consider where the data will be fed from. Will all navigation be driven from a master list in one location (your main intranet site maybe...), or will each section of the navigation have its own data source, in which it will be more complex.
At the end of the day you will be looking to biuld a web part for this that you will need to ensure exists in the master page of each site collection, and of course associated styles etc will need to be available within the feature itself rather than somewhere like the Style Library.
Potentially moving to Office365 is a major consideration for this type of development because the standard method described above usually requires the solution to run with "elevated privileges" and will be deployed as a full trust farm solution. You can't deploy this type of solution in Office365 and you will therefore need to look at creating a web part or app part that uses client side code to retrieve data from other site collections as full trust solutions are not available on SharePoint Online.