Try Nationwide for their basic Flexaccount. This account is available to bankrupts so they should not be concerned about past credit problems. I don't know what identity checks they carry out, but if he shows them the tenancy agreement and - if necessary - a letter from the landlord confirming that he pays all the bills commonsense should prevail.
It is not essential to produce utility bills to open bank accounts. The banks operate different policies and often say - quite incorrectly - that what they say they must have is required by the legislation. In fact they have a fairly wide range of options as to what documents they can accept. If necessary, he could ask to have it considered at a more senior level.