The garbling always starts and stops at the same time as the relay either opens or closes.
You are most likely getting interference from the electromagnetic field produced by the relay coil.
I am confident that the relay is not making any disturbances to the lcd but the 220v AC mains when connected to the relay even without any load, garbles the lcd.
In spite of your confidence the relay coil is still the most likely cause of the problem. The 220v ac mains, even without any load, can act like an antenna.
There are lots of previous forum threads on this topic. Try a google search for lcd relay site:arduino.cc.
Don