You are right that He goes to church on Sunday is the more common way to phrase this sentence; however, He goes on Sunday to church is not incorrect.
Changing the order changes the emphasis, so moving the indication of time draws attention to it. This is particularly useful in making parallel constructions:
He goes on Sunday to church, and on Monday through Saturday to drink at the pub with greater fervor.
You might also adjust word order to group or to separate words to avoid ambiguity.
In his religious studies class, on Easter Monday, he has a quiz on Good Friday in the Orthodox tradition.
Either Sunday or Sundays can reflect a habitual practice. On Sunday is more ambiguous, and could refer to a specific Sunday depending on context, whereas on Sundays invariably refers to multiple Sundays.