For the sake of future generations, I post my experience regarding this issue here:
This nonsense happens only after installing something other than Windows 8/8.1 in UEFI mode. Usually it's linux, but if it's not, god bless you, skip to solution #2.
SOLUTION #1:
Your only way to interact with UEFI is via your Linux system, so don't
[censored] it up.
Ubuntu/Linux Mint/Archlinux etc. for some reason don't install properly on Lenovo G580 in UEFI mode. I have no idea why, but they always register themselves in UEFI boot sequence as entry number one. And that's the exact reason why BIOS isn't accessible anymore, Setup Utility is always "Boot0000" (entry #1), therefore Linux overwrites it and UEFI doesn't know about Setup anymore.
Luckily, these great people, Lenovo engineers, integrated some sort of emergency default settings. When UEFI lacks an entry, it restores itself from these defaults. Problem is, after installing Linux Boot0000 is still there, even if it points to something different from Setup, it's still there and the solution is to remove it.
Code:
[sudo] efibootmgr -b 0 -B
That's it. There's no Boot0000, system will restore the default entry: "Enter Setup Utility". Your OS would become inaccessible, but who cares, there are plenty of guides how to restore it.
SOLUTION #2:
I personally experienced this kind of problem twice. And the first time I screwed up trying to find a solution like the one above. I practically bricked my laptop. If you were as stupid as I was, bring your laptop to Lenovo, they'll replace mobo for free.