“zero knowledge” encryption for mysql database

I have been looking at encryption for the database layer of my web application. It is using MySQL 5.1 (or higher, I can't remember offhand).

The application, managed by my organisation, stores data for public clients.

The easiest choice is AES_ENCRYPT/AES_DECRYPT which would help if a baddie somehow gained accessed to my database (assuming they didn't know the key).

However I want to take this a step further and prevent anyone in my organisation from being able to view any data stored for clients in its unencrypted form.

We use this premise for storing passwords; we encrypt the raw password at application level and compare it to a pre-encrypted pwd at db level. This is obviously a very common method, but we have that input from the user - the crucial difference with what I am trying to do is that we can't store an unencrypted 'key' and using the user's password is problematic because (aside from another heap of reasons) if they change it, all the encrypted data would have to be changed.

I can't get my head around this idea (you will probably have guessed I am not an expert in cryptography) but was expecting Google to throw up a few pointers. Unfortunately there isn't much I could find. I would be grateful for any pointers on where to start researching.

the crucial difference with what I am trying to do is that we can't store an unencrypted 'key' and using the user's password is problematic because (aside from another heap of reasons) if they change it, all the encrypted data would have to be changed

Those two ideas take you most of the way there:

Use a key to encrypt the data (the way you want to)
Instead of storing this key in the plain, use a user-password to encrypt the key
On user-login you compare their password against a one-way version of itself (hashed/salted, the way you normally would)
When that matches, you use the password to decrypt the data-encryption key
You then use this key to access the encrypted data

When a user changes their password, the key gets decrypted with the old password and re-encrypted with the new password. Minimal effort, no re-encrypting the entire dataset.

As I write this out, it seems obvious/trivial. I'm no crypto expert, and I need an answer to this question as well, so please poke holes in my idea in the comments.