This paradox, is a paradox to me only, probably because of my incomplete knowledge.
Assume a non-quasi-static process done on a gas for instance.
Internal energy of a system is a function of two of it's coordinates (if it has three). So it is defined, and exists, as long as our system is in equilibrium. So we have two value for initial and final internal energies in the process.
Work, however isn't defined during a non-quasi-static process since pressure is undefined when system isn't in equilibrium.
Now assume two conditions. If heat is defined during a non-quasi-static process, then work must also be defined during the non-quasi-static process, like this:
If heat is undefined during a non-quasi-static process, then internal energy, as the sum of two undefined quantities, must also be undefined.