"He comes on Monday at the latest."
Translation:Er kommt spätestens am Montag.
"Spätenstens am Montag" is a unit, here. He doesn't come "on Monday", but "on Monday at the latest".
So you could have "Spätenstens am Montag kommt er", or "Er kommt spätenstens am Montag".
Tekamolo has very little to do with the time complement being at the beginning of the sentence: It is about the order of complements among themselves.
The usual forming of the sentence has the subject first, then (mandatory) the verb in second position. Every variation introduces a change in focus and/or emphasis.
I have heard that usage with time "gegen dreizehn Uhr" meaning (if I understood it correctly) "not later than 1pm."
No; that means "around 1pm" (could be a little earlier, could be a little later).
"not later than 1pm" would be spätestens um dreizehn Uhr.
Can it be used similarly with days?
No. gegen Freitag sounds as wrong to me as um Freitag. Those prepositions simply aren't used with days.
Does the sentence mean that he will come on monday as the latest possibility, and not the days after it
or that on mondays he comes late (he comes around 7 on all other days, but on monday he comes around 8)?
That would be "He comes latest on Monday" / Am Montag kommt er am spätesten / Er kommt am Montag am spätesten / Am spätesten kommt er am Montag