This depends on what you’re actually trying to do.
If you simply wish to apply styles to a :before pseudo-element when the a element matches a pseudo-class, you need to write a:hover:before or a:visited:before instead. Notice the pseudo-element comes after the pseudo-class (and in fact, at the very end of the entire selector). Notice also that they are two different things; calling them both “pseudo-selectors” is going to confuse you once you run into syntax problems such as this one.
If you’re writing CSS3, you can denote a pseudo-element with double colons to make this distinction clearer. Hence, a:hover::before and a:visited::before. But if you’re developing for legacy browsers such as IE8 and older, then you can get away with using single colons just fine.
This specific order of pseudo-classes and pseudo-elements is stated in the spec:
One pseudo-element may be appended to the last sequence of simple selectors in a selector.
A sequence of simple selectors is a chain of simple selectors that are not separated by a combinator. It always begins with a type selector or a universal selector. No other type selector or universal selector is allowed in the sequence.
A simple selector is either a type selector, universal selector, attribute selector, class selector, ID selector, or pseudo-class.
A pseudo-class is a simple selector. A pseudo-element, however, is not, even though it resembles a simple selector.
However, for user-action pseudo-classes such as :hover1, if you need this effect to apply only when the user interacts with the pseudo-element itself but not the a element, then this is not possible other than through some obscure layout-dependent workaround. As implied by the text, standard CSS pseudo-elements cannot currently have pseudo-classes. In that case, you will need to apply :hover to an actual child element instead of a pseudo-element.
1 Of course, this does not apply to link pseudo-classes such as :visited as in the question, since pseudo-elements aren’t links.