How can I detect which customer has made a payment using only one receiving address? How can I detect which customer has made a payment using only one receiving address?

Can I embed a unique special message in the QR code (like a nonce) which I'll match against my database? Does it make any sense or is it too problematic (bitcoin client not embedding the message, unable to read the transaction message from the blockchain, etc..etc..)  

If that's not an option, does it make any sense to embed a unique code on the least significant satoshis? (let's say the last 3 satoshis if I expect on average less than 1000 transactions occurring at the same time)
You said you can't create new addresses on the fly but you also said you're using PHP. It's really easy to do it, just take a look at bitwasp/bitcoin-lib and give out a new address for every purchase. You can also create a functional mapping between a purchase id in your database and a bitcoin address really easily so you don't have to store the address used for each purchase.

Using the least significant digits of a transaction is a really bad idea. Not only because that'll cause a lot of trouble if people don't pay but also because you can't be sure that the wallets of all your customers support sending a very precise amount of BTC. Furthermore you'd have to discourage people from simply rounding up because they're too lazy to type in the exact value (if they have to type that in).