How can one be certain you won't hold onto the private key?
Through the magic of ECC, it is possible to generate a public key without the knowing the private key. That's how the Vanity Pool does it:
https://vanitypool.appspot.com/You must never allow someone to generate a bitcoin address for you if they can see the private key.