If you can have a secret key and it's fine for the party holding this key to also know the factorization, then yes this is quite easy.
Use your key to apply a pseudorandom function to the data you want the key determined by. If necessary use a pseudorandom generator to stretch the output.
Then use that output as the random coins for any standard ...
With Paillier, it's easy; generate a random encryption of 0 ($r^n \bmod n^2$ for random $r$ r.p to $n$), and then homomorphically add it to the encryption (that is, $C2 = C1 \cdot r^n \bmod n^2$), and you're done (and all you need is the public key).
I don't believe RSA allows this as a possibility...
The Paillier cryptosystem allows to encrypt integers modulo $n$. Therefore, if $m$ is bigger than $n$, encrypting it will lose most of the message - only $m \bmod n$ is retrieved through decryption.
To encrypt a message bigger than $n$, you must break it into blocks, which you encrypt separately. You can for example write $m$ in base $n$, as $m = \sum_i m_i ...
You made a mistake in decryption.
m = 1191*3 mod 35
You lost L(...) here. Instead of 1191 it should be L(1191):
m = L(1191)*3 mod 35
L(1191) = 34
m = 34*3 mod 35
m = 102 mod 35
m = 32
Voilà. We got the original message.