Which is correct: "via/on/in/with a messenger"?

It would depend on what you wish to say. Without a specific example I will interpolate.

He told me this via a messenger. would explain how his news got to you. The news received would be in a message not in a messenger. You would be told the news with a message. Or something in addition to the message came with a messenger. I would say shades of meaning would be more useful to the word message than messenger.