I gave up trying to get a Credit Card with Credit on my Work Permit a while ago.
Instead I applied for the BMO Travel Mastercard
. It's a prepay card and only costs $6.95 every year (previously $9.95 every 3 years). There's no special charges outside of regular credit card fees and you can top it up using Bill Payments from your bank account. The only downside is you can't get the money off once it's on (without paying a $3 fee anyway).
Another alternative is a CIBC Visa Debit card, since to most online merchants they process just like regular Visa. Useful for trips to the US too.