You don't need to create a new wallet every time.
You just keep your wallet (the software or hardware which holds your private keys) and give each client a new address to send the BTC to.
All of these addresses will be part of your (one) wallet.
You can't add a 'memo' when sending a transaction.
Any kind of 'memo' is just client-sided inside of your wallet. This won't be transacted via the network and therefore the receipent will not see it in any way.
The best simply is to create a new address for each payment. And if its too late for that, to request a signed message proofing ownership.