What is the difference between
"He always had a plan"?
"He always has a plan"?
The difference here is (as mentioned in the comment), that had is the past tense and has is the third-person singular form of the verb.
How does this change the meaning of the sentence?
"He always has a plan" usually means that the individual mentioned always has a plan for every situation.
"He always had a plan" can have two meanings. If the person referred to is dead, and thereby lived their life in the past, then the meaning is the same as for has.
However, it can also be used when recounting a series of events, when someone reveals they have a plan to resolve the situation the group is in. In the case, it is used to indicate that he has had said plan from the start.