Can I change an encryption key used without decrypting first
It's important to define what you want and why. For example, if the server doing the transformation does not hold the secret key of the first kind, then this is "proxy re-encryption". However, if it does hold it, then the question is why not decrypt first. From a security perspective it doesn't matter, and sometimes not from an efficiency perspective as well. 

If you are using ElGamal variant, then you can do this quite easily and it's actually more efficient than decrypting and encrypting. Given key pair $pk_2=h_1$; $sk=x_1$ and $pk_2=h_2$; $sk_2=x_2$ and given $c_1=(u,v)=(g^r \cdot m, h_1^r )$ you can compute $c_2=(u, v^{x_2/x_1})$. Check out why this works yourself...