Do support is required in questions where the verb and the subject are inverted, so
(archaic) See you that?
is replaced in modern English by
Do you see that?
Where the question word is the subject, it does not invert, so no do support is required:
Who said that?
Which train goes to Boston?
As in affirmative sentences, do is possible, but is ...
If so, is there a difference in meaning between "You always can trust me" and "You can always trust me"? I believe there is, because in the second sentence, "always" modifies "trust", unlike in the first sentence.
You asked if there is a difference in meaning between them. But then you say the position of "always" is the difference - that is not a ...
I think this is perfectly acceptable. It would be much less confusing when spoken, as you would naturally emphasise the second "had" (and maybe even shorten the "he had" to just "he'd"):
John talked about a spare key that he'd had made...