The straightforward solution is for the customer to sign a message with the private key used to sign one of the inputs in the transaction paying the bill. However, getting the wallet to provide the key is typically not straightforward, and I don't think any wallet provides an automated signing feature, which would be ideal for you.