I'm not 100% sure this is still the case, but I recall not being able to buy apps on iTunes using gift card credit a year or two back. I got the impression it had something to do with the way that software is taxed in Canada (Ontario specifically)—music and gift cards weren't taxed, but apps were.

So as far as I'm aware, you do need a credit card to buy apps, at least in Ontario.