Now, I think I understand how this all crap works. Leaving it here for next generations.
SaulGoodman provided almost complete solution for my case. What I had to do was to remove all Windows Boot Manager entries using efibootmgr tool as SaulGoodman showed, but I also had to create an entry for Linux distro with "Windows Boot Manager" label, not "LibreELEC".
Additionally, I have Windows 10 installed on the same disk as Linux. After booting into Windows, I couldn't boot into Linux's grub anymore. It kept booting into Windows.
It turned out that Windows is a sabotage. It keeps readding and reordering UEFI entries, placing himself on the top. What worked for me in this case was to reapply the same steps as before (removing all Windows UEFI entries, adding one for Linux with Windows Boot Manager entry, correcting order) AND disabling "boot" and "esp" flags for "EFI system partition" using GParted on Linux.
This way Windows thinks that this partition isn't UEFI anymore and doesn't modify entries.
Here's updated flow:
1. Create a USB stick with https://www.system-rescue.org/ on it.
2. Boot into SystemRescue.
3. Run following commands.
# identify all "Windows Boot Manager" entries that belong to Windows installation
efibootmgr -v
# run this command for all identified Windows entries to remove them, XXXX is the id of the entry
efibootmgr -b XXXX -B
# Add your Linux distro UEFI entry. Value for parameter -l differs form SaulGoodman's one. To know what to put here, check your existing Linux's UEFI entry using efibootmgr -v and use the same file path for -l param
efibootmgr -c -L "Windows Boot Manager" -l "\EFI\debian\shimx64.efi"
# Run it to verify if you newly created entry is the first one in boot sequence order. Look for "BootOrder"
efibootmgr -v 4. Now you should be able to boot into your Linux distro and change flags for "EFI system partition" using GParted.
Additional note: You can always boot into SystemRescue and modify UEFI using efibootmgr if something goes wrong.