First, if you have just move there, and don't have a bank account, you don't have checkbook either (there are countries who has no checks at all) - no check by mail.
No utilities accepted credit or debit card, they always wanted to have a proper bank account number from me. Later on they have improved their system and now they offer online bill pay, with an extra "convenience fee" for credit cards. Hurray! (Although I am not sure if the bank account is still a requirement for opening.)
Btw. similar story applies for wireless service: I was required to provide my full employment contract to receive a simple phone number (at that point I had bank account, active employment...). How weird is that?