when I lived in a house share, I wasn't on any of the utilities- various other housemates were, and I just paid them my share of the bill. The only "proof of address" I had when I lived there was my bank statement, which doesn't help if you need to open a bank account! All that to say that if you're moving to an existing house share where everything's been set up, it may be a bit difficult to get proof of address. If you can get your name on one of the utilities, do it! And council tax too- although my authority only sends a bill once a year so that wouldn't have been much help in my case.