First off, your definition is not IND-CPA: In the IND-CPA setting, the adversary has access to an encryption oracle. As you have already determined, no deterministic encryption scheme can be IND-CPA secure. I don't think IND-CPA is widely used for symmetric encryption though (although I might be wrong), semantic security might be a better option. For public key schemes, this is the same thing, but for symmetric schemes, it is not.

Semantic security informally says that you can't derive any information from a ciphertext about the underlying plaintext. Formally (from Katz and Lindell: Introduction to Modern Cryptography):

A private-key encryption scheme is semantically secure if for every PPT (= probabilitsitc polynomial-time) algorithm $\mathcal A$ there exists a PPT algorithm $\mathcal A'$ such that for all efficiently sampleable distributions $X = (X_1, \dots)$ and for all polynomial-time computeable functions $f$ and $h$, there exists a negligible function $negl$ such that $\vert Pr[\mathcal A (1^n, Enc(k, m), h(m)) = f(m)] - Pr[\mathcal A'(1^n, h(m)) = f(m)]\vert \leq negl(n)$, where $m$ is chosen according to distribution $X_n$ and the probabilities are taken over the choice of $m$ and the key $k$, and any random coins used by $\mathcal A$, $\mathcal A'$ and the encryption process.

If you look closely, you see that $\mathcal A$ has access to an encryption of $m$ where $\mathcal A'$ does not. The requirement is that this gives $\mathcal A$ no advantage, because for any function $f(m)$, the two do just as well.

Unfortunately, proving this kind of security is rather ugly, which is why (in public key cryptography, where both are the same) the IND-CPA notion is usually used. How to prove security for your scheme depends on your scheme, without further details, it will be hard for anyone to help you with that. The approach is generally to show something along the lines of "If an adversary $\mathcal A$ can break my system, I can construct an algorithm $\mathcal B$ (which calls up $\mathcal A$) that breaks problem $X$, but problem $X$ is considered hard". For example, RSA reduces to factoring in this way.

First off, your definition is not IND-CPA: In the IND-CPA setting, the adversary has access to an encryption oracle. As you have already determined, no deterministic encryption scheme can be IND-CPA secure. I don't think IND-CPA is widely used for symmetric encryption though (although I might be wrong), semantic security might be a better option. For public key schemes, this is the same thing, but for symmetric schemes, it is not.

Semantic security informally says that you can't derive any information from a ciphertext about the underlying plaintext. Formally (from Katz and Lindell: Introduction to Modern Cryptography):

A private-key encryption scheme is semantically secure if for every PPT (= probabilitsitc polynomial-time) algorithm $\mathcal A$ there exists a PPT algorithm $\mathcal A'$ such that for all efficiently sampleable distributions $X = (X_1, \dots)$ and for all polynomial-time computeable functions $f$ and $h$, there exists a negligible function $negl$ such that $\vert Pr[\mathcal A (1^n, Enc(k, m), h(m)) = f(m)] - Pr[\mathcal A'(1^n, h(m)) = f(m)]\vert \leq negl(n)$, where $m$ is chosen according to distribution $X_n$ and the probabilities are taken over the choice of $m$ and the key $k$, and any random coins used by $\mathcal A$, $\mathcal A'$ and the encryption process.

If you look closely, you see that $\mathcal A$ has access to an encryption of $m$ where $\mathcal A'$ does not. The requirement is that this gives $\mathcal A$ no advantage, because for any function $f(m)$, the two do just as well.

Unfortunately, proving this kind of security is rather ugly, which is why (in public key cryptography, where both are the same) the IND-CPA notion is usually used. How to prove security for your scheme depends on your scheme, without further details, it will be hard for anyone to help you with that. The approach is generally to show something along the lines of "If an adversary $\mathcal A$ can break my system, I can construct an algorithm $\mathcal B$ (which calls up $\mathcal A$) that breaks problem $X$, but problem $X$ is considered hard". For example, ElGamal reduces to the decisional Diffie-Hellman problem this way, which is related to (and a stronger assumption than) the Discrete Log problem.