Your idea of an encryption method including a nonce, and in a way that Alice cannot recover the nonce is practical; however it doesn't solve your problem.
One possibility would be a variant of El Gamal; in this system, Alice's public key is a value $A= G^a \bmod p$, with $a$ being Alice's private key, and $G, p$ being public parameters (with $p$ being a safe-prime, and $G$ a Quadratic residue).
To encrypt a message $M < p/2$, Bob would select a random value $r$, and generate the ciphertext $G^r \bmod p, M^2 \cdot A^r \bmod p$.
To decrypt the pair $X, Y$, Alice would compute $M^2 = Y \cdot X^{-a} \bmod p$ (and then take the modular square root of $M^2$ to recover $M$).
If Alice gets the pair $X, Y$, she doesn't know the value $r$, and so, at first glance, showing that $G, A = G^a, X = G^r, Y \cdot M^{-2} = G^{ar}$ are a DH set is the Decisional Diffie-Hellman problem, which is hard in general; she could easily do so by exposing $a$, however for her, that would defeat the purpose.
However, what she could do is generate a zero-knowledge proof that $G^x = A$ and $X^x = Y \cdot M^{-2}$ have a common solution $x$ (which she can do, as she knows what that common solution is); this zero-knowledge proof would show that $M$ is the decryption, without exposing her private key.
This leads to the more general observation; if the decryption algorithm $D$ and the public key generation $Gen$ both run in polytime, then the statement that $D(a, C) = M \land (a, A) = Gen(seed)$ (for a public $C$ and the $M$ that Alice claims is the decryption is a statement in NP (with $a$ and $seed$ being the 'witnesses'), and for such a statement within NP, one can construct a zero-knowledge proof, showing that $M$ is a correct decryption.
So, unless Bob can claim he didn't actually send the ciphertext $C$ (and I assume that somehow it is assumed that somehow everyone knows he did), it doesn't sound like a solvable problem.
