Printer head too low when printing Problem

My CR-10 printer seems to be trying to print the model 4 or 5 layers too low. This means that for the first few layers, the printing nozzle is forced against the bed, preventing extrusion until the print reaches higher layers.

Outcome

This results in the bottom part of the print having the internal structure visible and the printing head deteriorating. I had to remove the old nozzle because it was clogged up with what I believe to be some residue that was picked up during preceding prints.


note: On this print, the top part is almost-well printed. It cannot be seen in pictures, but I say "almost" because the well-printed part is still much thinner than expected. This is the result of my purposeful mis-leveling the bed so that the part where the printer "homes" is higher than the lower part. I did this to see if there was any obvious bending of the printing bed. Doesn't look like there is.

Fix attempts


I have tried to re-level the bed multiple times, but it doesn't matter as the "too low" effect is independent from the location on the bed.
I have tried using the printer's built-in Z-offset but to no avail. This might be due to the fact that I control the print through Ultimaker Cura 4, so I tried looking for the Z-offset property in Ultimaker Cura and even though internet says it exists, I failed to find it.


History

The printer used to work perfectly well and I do not remember having changed anything before the problem arose. I recently changed the nozzle and made sure to tighten it as high as possible but the Z-offset problem still persists.
Did you verify the Cura z-offset actually changed the corresponding G-Codes? 

I had the opposite problem on my RF1000. To fix the problem I added the following 2 lines to my start G-Codes:

M3001 ; Activate Z-Compensation 
M206 Z-0.3 ; Set z offset 0.3mm closer to the nozzle


The first line was default in some example prints and is (as far as I know) only used by Renkforce printers. The second line moves the nozzle closer to the bed. In your case you'd have to move it further away and would need a positive Z value.