Apple ID - Security questions reset
And that's the solution to my case.

I called to Apple Support and they said, that none of my additional e-mails was "rescue". I remember perfectly that in the time I registered my Apple ID there was no such option - just ability to set additional e-mail.

So, support reseted my security questions and now I can set a new ones, along with setting the rescue e-mail.