We had a similar experience as you. We needed a key management solution for PCI compliance and all the commercial products we saw were too expensive. Some key managers cost more than our product for small customers!
We ended up making a software based key manager. We made requirements and offshore developers coded it. At one time they were looking for other customers to use it. I don't know if they still are or not.
Let me explain the options we explored. First thing to remember is that PCI compliance and security are different things, you can be PCI compliant and not very secure.
Option 0 - Assign a key per DB column, and store keys in a DLL file. Your application links in the DLL file to access the keys to encrypt and decrypt the data. No one knows the keys. For periodic key replacement you make a new DLL with new keys, take down time to decrypt all data using old keys and reencrypt data using new keys. Then restart your application using the new DLL with new keys. (Note if you ever consider restoring a DB backup, you need to keep the old keys.)
The first time I heard about Option 0 I was surprised it was PCI compliant. We do not use Option 0.
Ways to improve on Option 0.
If you have an HSM in your environment, use the HSM to encrypt the keys in the DLL file. When your application starts it will decrypt the keys using the HSM. If you want more security, decrypt the keys every time they are needed.
Once your keys are encrypted, it is safe to store them in a DB table. If you assign each key (old and new) a small integer key-id, you can store the key-id with the encrypted data. That lets you do incremental key replacement and avoid down time.
Having your keys in the clear in memory in lots of processes, increases your exposure to a memory scan attack finding the keys. You can create a new process that is the only process that decrypts the keys. Your applications talks to this new process to encrypt and decrypt data. This new process should be on a box with a small "surface area" to protect it. Since sensitive data is going over the network now, this communications should be encrypted. SSL is a good option.