Will varying plaintext compensate for a fixed initialisation vector?
I recommend that you prepend a random 16-byte prefix.  Prepending a random 16-byte prefix, before encrypting with your CFB mode, will be just as good as using a random IV. The argument is pretty similar to Using CBC with a fixed IV and a random first plaintext block.

If we use CFB with an all-zeros IV and a random 16-byte value prefixed to the message before encryption, as you suggested, we get a scheme that looks like this:

$C_0 = 0$

$C_1 = E_K(C_0) \oplus IV$

$C_2 = E_K(C_1) \oplus PAN$

where $E_K(0)$ is a constant and $IV$ is your random 16 byte value. Since a constant xor-ed with a random value is itself random, the above has the same properties as:

$C_1 = IV$

$C_2 = E_K(C_1) \oplus PAN$

which is the standard CFB construction (with a random IV) with different indices.



Strictly speaking, the 16-byte prefixes don't need to be random.  The above approach is probably secure as long as the 16-byte prefixes are all unique. If you pull 16 random bytes from a well-seeded crypto PRNG, they should all be unique. But I don't trust your other schemes to produce unique values.  Therefore, I don't recommend using any of your other approaches.



Note that while this technique of prepending a random prefix works for some modes, such as CBC or CFB, other modes, such as OFB or CTR are totally broken in such a scenario.