Hi Aurelius,

You have not stated how many km per day or what sort of bikes you are riding?

But my suggestion would be to cycle something like this to Trondheim.

http://www.ridewithgps.com/routes/43181354?privacy_code=GhqBYhm34QeSJazN

Do your own research before heading out. There are some sections on main roads, long tunnels, and gravel sections. But any long-distance routes on the west coast will feature these as there are limited roads. If you cycle 100km a day, then it will take you 10 days, leaving you 3-4 days to get back to Bergen.

To get back to Bergen you can either take a train to Oslo and then Bergen (long but doable) or take the Hurtigruten boat back. If you want to pay only for a desk ticket, you will need to book Trondheim – Ålesund and then book again in Ålesund – Bergen. You can only book a deck lounge ticket for under 24 hours of travel at one time.

If you feel Trondheim is too far to go, then you could cycle to Ålesund or Molde and take the boat back from there.

Here is a shorter version with additional info about what to expect:
http://www.ridewithgps.com/routes/39585068?privacy_code=cMFIu2stzKku6Ugm

Good Luck!