Are PBKDF2 derived keys related if only the number of iterations is changed?
Leave the iterations the same, they should be determined by the CPU time. 

Instead provide a different random salt to PBKDF2 on each encryption, you can just concatenate the salt to the encrypted data, it does not need to be secret.

Of course for CBC you also need a new random IV for each encryption, it too can be concatenate to the encrypted.

You should also MAC the encrypted data so that you can determine ion the decryption succeeds, that is the correct key is used.