The only time I "needed" a credit card is when I tried to sign up for some US company's service. It rejected my debit card because it wanted credit, so I just took my business elsewhere.
Other than that, I've rented cars, rented other things with a "X will be charged to your card if you return it late", unattended gas stations... all the usual places you'd think need a credit card. It's fine.
We do have a "negative limit" that banks often give you, which means you can go into the red and pay it back later, but that has nothing to do with the card, it works even for normal bank transactions.
I had a car rental in Oslo that only allowed debit cards if you took out their full insurance. I was already insured, we rented though some sort of front, but they only allowed that on a credit credit card.