Your confusion comes because you think that you can only write $\Delta U = C_V \Delta T$ only for isochoric processes.
The specific heat at constant volume is defined as
$$ C_V := \left(\dfrac{\partial U}{\partial T}\right)_V \tag{1} $$
Eq.(1), as it is written, denotes $C_V$ as a state function.
The changes in internal energy are always given by
$$ \int_{U_1}^{U_2} \mathrm{d}U = \int_{T_1}^{T_2} C_V(T) \mathrm{d}T \tag{2} $$
if
- The fluid is an ideal gas, or
- The process is really isochoric, independently if the fluid is an ideal gas or not.
To make sure that the formula works even though the process is not isochoric, take a look at the following image, where you are interested in the $\color{purple}{\text{path}}$ in purple:
Since for an ideal gas $U$ is only a function of $T$, if we plot $U$ vs $V$ we get straight lines. Lets calculate then, by virtue that $U$ is a state function, the change between those two arbitrary points by the $\color{red}{\text{path}}$ in red
\begin{align}
U(T_2,V_2) - U(T_1,V_1) &=
[U(T_2,V_2) - U(T_1,V_2)] + \underbrace{[U(T_1,V_2) - U(T_1,V_1)]}_
{=0 \; (\text{constant $T$}))} \\
U(T_2,V_2) - U(T_1,V_1) &=
\underbrace{[U(T_2,V_2) - U(T_1,V_2)]}_{\text{real isochoric process}} \\
U(T_2,V_2) - U(T_1,V_1) &= \int_{T_1}^{T_2} C_V(T) \mathrm{d}T \tag{3}
\end{align}
In the last derivation we "assumed" that we could only replace $C_V \; \mathrm{d}T$ if the process was isochoric. In Eq. (2) we didn't assume anything, and the result was the same.
I am wondering why in this last equation are we relating $C_V$ and $\mathrm{d}V$ while $\mathrm{d}V$ is $0$ as the given specific heat is at constant volume. How to justify that in the last equation, if process is at constant volume, that $C_V$ is being related to $\mathrm{d}V$ anyways?
If you add that the process is indeed isochoric, in addition to that it was also adiabatic, the first law will tell you $\mathrm{d}U = \delta q + \delta w = 0 + 0 = 0$. For a simple fluid that has two degrees of freedom, asking for two restrictions leads to this behaviour: nothing has happened to the fluid. You will arrive to the same conclusion if you demand an isentropic and isenthalpic process, or a constant pressure and constant volume process, etc. Ask for two restrictions and you will get always $U_2 = U_1$.