If you look at the Merriam-Webster dictionary, two of the example usages for via are as follows:
He did some research via computer.
We went home via a shortcut.
So the second example shows you can certainly use a after via. ("We went home via shortcut" sounds wrong to me.)
However, I would say via telephone. This usage is closer to via computer, because telephone here refers not to a specific telephone, but to the general medium of telephony. Similarly, you would go somewhere via train or via superhighway, if you are talking about trains or superhighways in the abstract; but via the Orient express or via the Mass Pike, if you are talking about a specific train or superhighway.
If you are talking about a specific telephone, I wouldn't use via; I think you have to say something like "I called her on my cell phone."