AES: Is it safe to encrypt same cleartext with same key but with million diferent IV?
No, for the same reason that you can't crack 1.3 million ciphertexts knowing they use the same key but different plaintext. 

As long as the CSPRNG you use to get your IVs is strong, you're safe.

You are correct in that decrypting the first block without the right IV is not possible. If it were, we wouldn't be using CBC. But yeah, if he could somehow guess the right IV and key for a certain block, he'd be able to decrypt all the following.

For situation 2 take a look at this question.