AES: Is it safe to encrypt same cleartext with same key but with million diferent IV? The encryption mode that I am using is CBC. Algorithm is AES and the key size is 128bit.
I will be encrypting a 36 byte string over 1.3 million times with the same key but with a random IV.

My question, as the title states, is it possible to reverse engineer the key for 1.3 million cypher texts without knowing the key nor the IV but with the knowledge that all the clear texts are the same.

From experience I know, it would not be easily possible to decrypt the first block without the right IV but how would the security of the rest of the block be impacted ?

Edit:

Situation 2: will knowing some portion of the clear text make it easier to guess the key ? Suppose the data is padded using PKCS7 specifications effectively making, lets say, the last 12 bytes of the clear text to be "0c 0c 0c 0c 0c 0c 0c 0c 0c 0c 0c 0c" as the string is 36 byte long.

An easy solution would be to fill the last 12 bytes with pseudorandom data. However, I am interested in knowing the consequences of not following such an approach.
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.