It can be done - we set up an HSBC Canadian account from the UK before coming out here. I can't remember exactly what we did (sorry) but it was something like this:
- contacted HSBC in UK and asked about opening an account in Canada
- they put us in touch with the Canadian side and we opened an HSBC Canadian internet account over the phone through them, then deposited cash into this account via an FX broker.
This is not a recommendation or otherwise for HSBC - the same approach may work for other banks, this is just what we ended up doing.
Once you are over here you will find it's easy to get another account, particularly after a few months of building up some credit history. You may find the limits on your account and credit cards etc. rather low for a while, but it rapidly improves.