How to renew keys for a statically-encrypted database Preamble

Before I ask this question, please accept that I fully understand that 'rolling your own' is never a good idea, and that I am a relative n00b. The only reason I am doing this the way I am is that there are major constraints - I have no high-level crypto libraries (like, say, NaCl) available, and this will run on a mainframe. The crypto API I must use makes initialisation vectors my responsibility, but not keys -- I simply present a key token, and encryption and decryption are performed elsewhere in a 'leakproof' part of the system. So please don't criticise me for my environment, and please recognise that 'don't' do anything' is not an option.

Environment


A legacy database which will contain credit card numbers (PANs)
The PANs will be encrypted to protect against unauthorised online access by (eg) sysadmins and offline access to backups of the DB
A single key will be used for all PANs
Cipher will most likely be AES256 in CBC mode (the API may restrict me to ECB mode, but I'm trying to change that).
Each PAN will be encrypted with a different initialisation vector, which will be stored with the encrypted PAN
PANs are constantly being purged from the system. We can establish a maximum lifetime.
Storage space is limited -- I can pull an extra 16 bytes for the IV, but any more will be hard.
It is not practical to scan and update the database if I want to change the single key -- the DB runs at about 40,000 I/O per second for most of the 24-hour day and the system runs non-stop.


The Challenge

Find a way to be able to expire the single key and introduce a new one 

The Proposal

Here's my current thinking, which I recognise has weak points.

Cryptographic keys are generated, and stored encrypted under a master key, in a completely separate component of the system, with its own access rules. Keys are identified for use by an alphanumeric key token.

At any time, I have two available keys, called 'A' and 'B'

For encryption:


Obtain a 16-byte cryptographically sound random number
Set the last bit on, signifying key A
Call the encryption API with the resulting IV, and key token A
Store the IV and the encrypted data


For decryption:


Test the last bit of the stored IV
If the bit is 1, select key Token A; if not, select key Token B
Call the decryption API with the IV and the selected key token


Now, when I need to expire the key, I simply need to change the encryption to set the last IV bit off and use key B. Decryption does not change.

Around six months later, when I have no more A IVs left in the system, I can swap again.

Each time I swap, I can generate a new key for encryption from this point on.

My questions are these:


If I cannot obtain a cryptographically sound random IV, just how bad would it be to use a high-resolution clock? The clock I have in mind is high-resolution (10 nanoseconds or better, and guaranteed not to repeat, as I won't be doing more than about 10k encryptions per second). I understand that the IV should not be predictable, but just how (precisely) predictable is such a clock?
I have to cater for the possibility that a PAN may get left over from a previous key which is no longer available; for example, a PAN which was encrypted with an earlier A key, but which fails to decrypt with the current A key. Assuming I don't want to increase the number of bits I 'steal' from the IV, is there a good, simple way to verify that the decryption is with correct key. I'd prefer to avoid the extra overhead of something more complex, like, say, an HMAC. Suggestions?
Any other comments or criticisms (within my constraints)?
Some remarks:


a 16 byte IV is required by CBC, but you may not require a 128 bit unique value for your protocol
CBC relies on an IV that is indistinguishable from random to an attacker, fixing bits in the IV is not a good idea
CBC requires a padding mechanism, unless you can use ciphertext stealing


Now a few calculations reveal that if you rely on the non-repeating counter, that you need an number of 8 bytes to have enough precision (584 years should be enough). Store just this number. You can create a good IV from this number by pre-pending the number with zero's and performing a single block encrypt (in the black box of course).

Now you have got 8 bytes left. I would suggest you use these for the key indicator (make it one byte instead of 1 bit, to avoid key management issues later on). You could use the additional 7 bytes for storing an authentication tag, so that nobody can change the ciphertext (and thus the PAN) unnoticed.

Finally note that the "default" padding mode for CBC mode of operation, PKCS#7 padding mode, will use 1 to 16 additional bytes of overhead. This is overhead you can sorely miss on size constrained systems, especially since it can be avoided without penalties on the security of the protocol. Look up ciphertext stealing, or go with another mode of operation that does not require padding.

This answer is provided as is. I remain convinced that you should hire a consultant that has experience protecting credit card related data.