Pay-as-you-go SIMs can be bought at pretty much any gas station, 7-11, Mac's, Koodo, Fido, or Virgin booth with cash, without showing ID. Some of them require you to fill in an online form to activate the SIM, but you can put any info in there you want, and "payment" is done using the code on the receipt instead of credit card.
Just went through this process to get a Koodo SIM for friends visiting from Australia. No ID required, no paper trail created.
No regulation on this up here (Canada) that I can see.