First the thing struck me was use of "shall" because "shall" has taken it's place pretty much in language museum. It appears via the Wikipedia article that it is a term originated in middle ages. So I thought "shall" might be possible. But I could not understand how "shall" is being allowed with "he" here. If I remember correctly, I read a rule in English Grammar in my childhood that if a subject in a sentence is emphasizing that he certainly will do something in future, then "will" follows "I" and "We" and "shall" follows rest of the pronouns. Is this rule being applied here? Or it is as it is from it's birth?
It's a neologism.
A survey of Google Books finds exactly one instance of the version with shall before 1980, and that's in 1962. Before then the verb is doth appear or will appear or 'll appear or simply appears.
Versions with shall begin to flourish in the 1980s. Significantly, they all derive from popular fiction; in scholarly works the older forms are employed.
The 'rule' you refer to was still operational in my childhood, but in the last two generations shall has almost disappeared from the language. That means that there are fewer and fewer people left who know how shall used to be used; so novelists who don't know any better, and whose audiences don't know any better, use shall appear without reproach to give either the proverb or their settings a flavor of archaism.