Since the fix was preformed by someone else, I cannot describe the exact process, but I'm reposting the general instructions as an answer.
Contrary to what I believed, it appears that it is possible to change the language of Windows Server 2012 in control panel, it's just the option wasn't very obvious to me. Switching this option makes the system do a big patch which might leave you with no .Net runtimes (and possibly other libraries, system tools). Although you might be forced to reinstall those, thankfully you should be able to do so in the language of your choice. When I have time to test it further, I'll post more info as an answer.
For now, if you have a similar problem,
- Try going to "Control panel"
- Open "Clock, Language, and Region" section
- And then the "Language" subsection
Within this section make sure the language, that you want your .Net (and validation messages) to be in, is there.
If it's not, just add it and follow to the next step:
- Click on the "options" hyperlink(like) button (on the right of your language row)
- Wait for the "Windows display language" section to load (previously I didn't bother to do so and missed the next option as a result)
- Pick the "Download and install language pack" option and follow with the installation (it might take a while)
After doing this, it should be possible to install the correct language pack for your .Net.