Wikipedia says that the -ta in Lithuanian and Polish is from Latin thea, from the phrase herba thea ('tea herb'), so there is still a morpheme in common with the other languages in this case!
Interesting, I never actually encountered "czaj" used to describe tea. From a quick search it seems to be either prison slang, or a word used in eastern Poland, coming from Russia.
In the area where I come from (Wielkopolska) czaj is a commonly known word for a "strong tea-like infusion". It's not prison slang at all, but of course there might be regional differences in the usage of this word.
Herbata seems to come from Latin, as it relates to herbs.