How to renew keys for a statically-encrypted database
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.