I have located the problem with help from my colleague (Vitezslav Crhonek, maintainer of texinfo). For some reason, the newer version of texinfo (6.1+) is unable to fallback to different fonts when some other fonts are unavailable.
* I was able to compile documentation for gawk-4.1.3 & gawk-4.1.4 with texinfo-6.0
* I was able to compile documentation for gawk-4.1.3 with texinfo-6.1
* I was NOT able to compile documentation for gawk-4.1.4 with texinfo 6.1
* I had to add installation of missing fonts into build root (texlive-ec, texlive-cm-super in Fedora)
My guess is that you have switched to new fonts for Index of documentation, or older texinfo was able to get over missing fonts before so nobody has noticed that problem.
I hope this can help to other people in the future in case they stumble upon this problem as well.
Thank you guys for your time.
P.S.: gawk-4.1.4 will be ready in F26. I have another question regarding this, but I will post it to separate thread to not pollute this one.