Do It Yourself Credit Card Storage (PCI - DSS Compliant)
The PCI DSS isn't expressly clear on this topic. The meaning of secure key storage and secure key management is left up to the QSA's interpretation. You may find that that one QSA considers the private KEK to be all that needs to be secured, and he treats the EKs as tokens. Or you may find a different QSA that sees every individual EK as needing to be secured, even though they've been encrypted with a KEK. We've had both kinds of auditors, and frankly, I thought the "harsher" of the two was more competent (even though I disagreed with his assessment of the risks.)
The bigger problem I see is that you're not taking into account the cost of owning this system. A complex system like this is going to take time and money to build. It will require the auditors to make a very careful examination of all the nooks and crannies of the systems, which will also take a lot of time and money. And they'll have to repeat their examination every year.
Consider that under the current rules, if you build a system that gets breached, the rental guy will be liable for 100% of the costs of all fraud associated with the breach. That means if someone steals a millionaire's card and charges a Ferrari on it, he's liable for the loss. If someone steals 10 millionaires' cards and charges one Ferrari on each of them, he's liable for the whole loss. His lawyers, of course, will immediately turn around and sue you for building an insecure system. And they will sue the QSA for incompetence at not telling them that your homemade system was insecure. So the QSA has to charge enough not only to pay for the time spent auditing the system, but also some insurance to cover their risk.
Frankly, the rental guy would be better off having his counter employees making photocopies of customer ID cards and dropping the copies into a drop-box type safe under the counter; and keeping his security cameras rolling. If a customer fails to return an item, or returns a damaged item and contests it, he'll have the evidence he needs to bring the renter into small claims court. That's a whole lot cheaper than building a PCI DSS compliant system and maintaining it. (And that's really the point of the PCI DSS - the auditor should identify and explain the risks, the business owner should carefully consider the risks, and then make wise choices.)
Well, referencing the "PCI DSS and PA-DSS Glossary of Terms, Abbreviations, and Acronyms" we can see the following listed for "strong cryptography"
Strong Cryptography: Cryptography based on industry-tested and accepted algorithms, along with key lengths that provide a minimum of 112-bits of effective key strength and proper key-management practices. Cryptography is a method to protect data and includes both encryption (which is reversible) and hashing (which is “one way”; that is, not reversible). See Hashing.
At the time of publication, examples of industry-tested and accepted standards and algorithms include AES (128 bits and higher), TDES/TDEA (triple-length keys), RSA (2048 bits and higher), ECC (224 bits and higher), and DSA/D-H (2048/224 bits and higher). See the current version of NIST Special Publication 800-57 Part 1 (http://csrc.nist.gov/publications/) for more guidance on cryptographic key strengths and algorithms.
Note: The above examples are appropriate for persistent storage of cardholder data. The minimum cryptography requirements for transaction-based operations, as defined in PCI PIN and PTS, are more flexible as there are additional controls in place to reduce the level of exposure. It is recommended that all new implementations use a minimum of 128-bits of effective key strength.
Generally speaking, you can just use a symmetric encryption algorithm, your encrypting it and then decrypting it before using it, this can be done by the database.
To answer "Am I doing this correctly?" I would say no. He needs to have tokenization, it will make his life easier and cheaper, he will need to be fully PCI DSS compliance and need to do self assessments each year, which he probably won't be compliant given his reluctance to do tokenization because he likes his processor (what processor doesn't support tokenization in this day and age?). And with tokenization you don't have to worry about any cryptographic architecture since the token does not have to be cryptographically secured.