I don't know about in the US, but I live in a fairly small city in Canada and we have DVD rentals. I go to the video store almost every week, and it was on the papers that a second one (which will also rent out VHS!) is opening.

The Library does DVD rentals too, I check it out every couple of months.

It's even better in Toronto, Bay Street Video is an institution.