Appears that your provisioning profile doesn't contain the key that you uploaded with it. I'd suggest recreating your provisioning profile and ensure you are using the same key that you upload.
I tried it multiple times with every combination, never worked
Not much I can do with your response, other than tell you that the output of our build log shows that your uploaded signing key has serial "3035..." and the uploaded mobileprovision only contains one dev key with serial "7415...". These should match. If you haven't already I'd suggest repeating the key export from scratch.
Note that you are building with a distribution cert.
I have the same problem and tried everything possible. On my MAC I can compile an iOS app with the same p12 and provisioning profile without any problems.
Could you take a look in the log, if the serials are matching?
Hi Jens -- exact same answer as above. We're showing a different key in your provisioning profile.
Again, possibly noteworthy that you too are using a distribution profile.