Can a change in internal energy always be expressed as the product of the constant volume heat capacity and the change in temperature?
The statement in the title question "internal energy [can] always be expressed as the product of the constant volume heat capacity and the change in temperature" would only apply to a calorically perfect gas.

If you instead said "an infinitesimal change in internal energy can be expressed as the product of the constant volume heat capacity and an infinitesimal change in temperature", that is only true for a thermally perfect gas.  

For real gas, the heat capacities depend upon both temperature and pressure.