Replacement for XOR in CBC?
Without completely restructuring how CBC mode works, that would not appear to be possible.

Your generalized CBC mode encryption would be defined as:

$$C_i = Enc_k( P_i \circ C_{i-1} )$$

for some operator $\circ$ (which need not be commutative, or even associative).

What this means is that, during decryption, we have:

$$Dec_k(C_i) = P_i \circ C_{i-1}$$

To make decryption, that is, the recovery of $P_i$ feasible, we must have an easy way, given $A, B$, to find the solution $x$ for $A = x \circ B$.

In the problem you're asking to be infeasble, that is, $P_i\circ C_{i-1} = x\circ C_{j-1}$, if we set $A = P_i\circ C_{i-1}$ and $B = C_{j-1}$, we see that must also be an easy problem (otherwise decryption would be difficult)