I am interested in theoretical answers, assuming there is infinite time for decryption.
We call such an attacker a 'computationally unbounded adversary'
- Is it necessary to work out the private-key exponent for decryption? Are there no alternative options?
One approach that a computationally unbounded adversary could is as go through all possible values $M$, and find one which has $M^e = C \bmod n$; such a message $M$ is the decryption of the ciphertext $C$.
This approach actually takes longer than the more traditional approaches that involve factoring $n$ (and from that, rederiving the decryption exponent); however a computationally unbounded attacker might not care.
- Can a message encrypted using RSA be decrypted using only the public key? If so, how? If not, why?
Actually, there are a number of different ways that RSA could be decrypted by a computationally unbounded attacker
They can brute force the message (as listed above)
They could factor the modulus, and rederive the decrypion exponent
As pointed out here, they could generate every possible public/private keypair, and pick out the public key that they actually see. Any public key cryptosystem can be broken by this method.
So, if RSA can so easily be broken by a computationally unbounded adversary, why do we still use it? Well, we don't believe that computationally unbounded adversaries exist, and so that's not considered a real world requirement on crypto systems. Actually, if they do exist, we don't have that much in the crypto toolbox that they can't trivially break anyways.