This is tricky stuff, and you may have to give. But there are some things you can do.
First, to settle any doubt, you are absolutely correct. A company does not need to know your SIN if they are not deducting personal tax, and they should not be deducting personal tax from payments to a contractor. It is illegal in Canada to deny someone service because they choose not to provide their SIN, and the government does take seriously the issue of people asking for SINs when they don't have to.
Start by quoting the government statements on the matter. That page is a good place to start, and it also gives some advice on what to do if you are asked for your SIN inappropriately. Send them the page and follow the advice. In particular follow the advice which says to ask detailed questions about what the SIN will be used for.
I'd lay pretty good odds that you are dealing with a junior staffer who has just been told "ask for their SIN" and hasn't been given any other information. If they can't tell you what it's going to be used for that would make the odds even greater - and you can tell them that if they don't know what it will be used for then you don't need to give it to them.
Probably your best bet is to talk to someone more senior, or make them talk to someone more senior. Someone in the legal department instead of finance or HR would be better.
I would personally take quite a stand on this, but in the end if they absolutely refuse to listen to reason or legality it may be simpler to just give them what they want.
If they aren't going to use the SIN, then you might consider giving them a fake SIN, since it won't make any difference. You can always claim it was a mistake if they ever find out - they aren't going to bring legal action if they weren't legally allowed to collect it in the first place. I did that once to a company who demanded my SIN, but swore that it was "only to distinguish duplicate records in the database". I have a very unusual name and the chances of having someone on their payroll with the same name is zero.
EDIT: All of the above assumes you are doing work through some kind of small company, like a "sole proprietorship". This is normally how things are done. If you are contracting as a private individual, without any kind of company, then they may need your SIN because they have to treat you like an employee.