Since nobody has responded yet I thought I'd jump in! My parents did the opposite about ten years ago (moved from Canada to the US). It's not the best situation, but they ended up getting a copy of their credit report from Canada, and that combined with letters from their employers were enough for them to rent for the first couple years before they could build up their credit. Something like that may work for you as well, especially if you explain the situation!
They may ask (or you can offer) to have someone co-sign the lease as well. Good luck and enjoy Toronto!