So, as for animals you're not supposed to use the Genitive but Accusative case when it comes to negation? :/
For masculine singular it is taken into consideration if the noun is animate or not - animate has acc=gen (Widzę konia, psa, strażaka) , non-animate has acc=nom (Widzę stół).
For masculine plural - if the noun is personal or not - personal has acc=gen (Widzę strażaków), non-personal has acc=nom (Widzę psy, stoły, konie).
So the horses jump into the second group when in plural ;)
If the masc. animate, genitive ending is -a why is it not 'kona' rather than 'konia' as written here?
It's mostly an orthographical thing. The nominative for horse is „koń”. If it were „kon”, then indeed the genitive form would be „kona”. In case of „koń” you would want to also add „-a” and you would get „końa”… which is nice and all, but Polish orthography rules don't allow you to use consonants with a line above them right in front of a vowel (if it's in the same word). In cases like this you have to use „ni” instead (or just „n”, if it is in front of „i”).
Would "cannot" be accepted here, or does that interfere with the sentence too much ?
So for masc animate, gen = acc. But this is not the case for "mezczyzna/mezczyzny" because mezczyzna is personal? Is that correct?
Actually, no. The reason for that is because „mężczyzna” ends with an „a”, so even though it's a masculine animate noun, it will inflect into different cases like a feminine noun.
The distinction between personal and non-personal nouns of masculine gender only matters in plural.
'They hear no horse' is also correct English, although a little less commonly used.
That would also be correct. Oni is used with all-male or mixed-sex groups, and one is used for all-female groups (or inanimate objects).