As a Canadian, is there any way for me to prove my residence? I don't pay utilities, my cell phone is paid with the cable bill as it's cheaper bundled, and I obviously don't have private health insurance. They won't even take bank statements, which seems ridiculous to me.
You can make a fake one, cause they rarely bother with checking it out, just type your address and personal data correct. It's not like they are going to get in touch with a company that should send you those bills. I used my cable bill for my verification at Bitstamp. It was a pdf which i printed out to scan it again in a weird angle. That was enough for me.
But I would suggest against gox, they have high fees and waiting times. For me living in a EU Bitstamp is a no-brainer.