1) since you have a work permit until September 2017, you can send your application anytime though sending it sooner would be better since it takes longer to process process some applications these days. You can even send your application Outland which is faster than in-land application though if you do Outland, you won't be able to qualify for an OWP after your Work permit expire. You would also benefit from sending it In-land and get an OWP sent with your application though you might wanna send the OWP application before December 2016 to take advantage of the Spousal OWP pilot project since we don't know if they are gonna extend it for 2017. But then again, you have your Work Permit till 2017 so you have an option, whichever would work best for you.
2)In regards to you question about Common-Law, I can't answer that one for you but if you're planning of sending your application soon, you might be better of going on marriage option if you have a gap. But getting married too would take a little time since you have to register then get married and after that, wait for your marriage license. Though being married is the best option, you have to decide if you actually love each other because being married is a big move, it's a lifetime commitment.
Do you know how long does the process for marriage usually takes? and we are planning to get married, but I'd rather do the common law right now, which seems a bit unclear as if we are considered common law or not , because of the gap... Somewhere in CRA website, it says if you are away for family visits for less than 90 days, you dont have to notify CRA regarding your common-law status. which I guess means the status won't change for being away for less than 90 days...not sure
For police background check, you have to go online and check the RCMP or accredited offices that does finger printing electronically (electornic finger printing takes less time and more convenient if you're planning of getting police certificates abroad where you have lived for more than 6 months within the last 10 yrs or when you were 18 whichever comes first) the fimger printing agency where I went does the RCMP and abroad finger printing too, most of finger printing agency does) tho they asked me if the country where I would get my police certificate requires finger prints because some country doesn't. Try to go online and check where the nearest finger printing agencies are in your province. It depends too (if the country where you would need a police certificate) look at the cici website and it will give you a link of each countries website (where and how to obtain police certificate abroad)
