The program through which you obtained residency is a key factor. If your residency was determined through any program run outside of Quebec, it may be tricky for you to provide a QC address. However, your options are:
1. Try providing the Montreal address to the IO. If they accept it, fine, but if your residence was issued through the FSW or a PNP, they'll most likely reject it.
2. Rent a UPS mailbox. Whereas its like a post office box (which CIC does not accept), the address is actually a street address in the format below:
000 Street Name, Suite 888,
City, Postal Code, Province
The suite number is your box number.
This option requires, either you land first then rent the box (see option 3), or you contact UPS stores in the province you intend to settle (advisably closer to your place of residence/accommodation for your convenience). Visit www.ups.ca and use their store locator tool for a list of stores within your destination that offer the rental service. Contact details are indicated for each store, call them and determine if you can set up the box remotely, some do.
3. Land without an address and provide it after you get one. In this case the IO will provide you with an Address Notification Form that you can fax to CIC within 180 days from your date of landing. However, you can do it online as well within 180 days.
4. If you've already reserved a place for temporary accommodation (e.g. airbnb), and intend to stay there for 2-4 months (card processing is 56 days), you can obtain approval from the host/owner to use the address during your stay. If the owner approves, you can provide that, but you have to hope the card gets there within the time you plan on staying there.
Those are your options.
