MMMMM interesting question ... Your name almost certainly would not be on the utility bills as they would be in name of the owner . So maybe you would have to request the owner add your name to the contract .Alternatively , if you have a Spanish mobile phone then correspondance would be sent in your name .. that would probably work .
As I remember ( and I'm surprised nobody else is input on this ) when you go with your documents to the police station they will stamp various official documents which you then take to the ministry of work and social security who will issue an NIE number on the spot . MM - Is this right ? .. I know you've been through this too and my memory is terrible .