Hello, Katie, and welcome to the Grammar Exchange!
What is the correct/logical structure here?
In every one of your examples, both options are correct. This includes your first example. It is correct to use "was" ("I met a man yesterday. His name was John."), even if the man you met yesterday never had a name change. Of course, it is also correct to use "is": "I met a man yesterday. His name is John." The difference is that, in the version with "was," the second sentence expands upon the time domain of the first, such that "was" is relative to "met."
Something similar happens in the other sentences, where you have used a subordinate clause following a verb of speech in the past tense. In the editions with "was" in the subordinate clause, "was" is a relative tense, falling within the past-time domain of the past-tense verb of speech, such that it expresses present meaning relative to that past tense. This is sometimes called "backshift."
He told me, "My name is John." <--> He told me that his name was John.
Now, it is also O.K. to use the present tense in the subordinate clause: "He told me that his name is John." Apparently you have found test guides that misinform people that they should do that. With so-called eternal truths, the non-backshifted form is always an option. I myself think it sounds better to use backshift even in such cases: "People believed that the earth was flat." In a variation of your last example, however, I might opt for the present tense:
(1) He informed me that he was in the military.
(2) He informed me that he is in the military.
In (1), it is not obvious, outside of context, that "was" is a relative tense, such that the hearer or reader should assume that he is still in the military and was in the military at the time that he informed you that he was. My natural assumption would be that "was" was a backshifted, relative tense. But it might be helpful to use "is" just to clarify that it's not an absolute tense. (Absolute tenses are relative to the time of speech.) Sentence (1) should not be read as meaning (3):
(3) He informed me that he had been in the military.
Please note how clear the temporal reference of the subclause is in (3). ♣