This is an example of what is sometimes called the "Marquee Effect." Think of the light bulbs surrounding an old-fashioned movie theater marquee, where the light bulbs turn on in sequence to produce the illusion, from a distance, of a light source which is moving around the the marquee.
There is no limit on how short the time interval is between one light turning on and the next turning on, so the perceived light source position can move arbitrarily fast, but in fact nothing is actually moving at all.
In the case of the television screen, the phosphors on the screen can be lit in rapid sequence, but the electrons in the beam do not ever need to move at (or even near) the speed of light.
More generally, there are loads of examples of some imaginary or conceptual "object" moving faster than light, but in all these cases there is nothing actually moving at all. A classic example is the intersection point of two nearly parallel lines, which moves very rapidly as the angle between the lines changes. In this case it is obvious that the moving "object" isn't moving at all, but its still a good example of a case where you can discuss something moving faster than light without there being any violation of physical law.
A tachyon is a particle with an imaginary rest mass. This however does not mean it "travels" faster than light, nor that there's any conflict between their existence and the special theory of relativity.
The main idea here is that the typical intuition we have about particles -- them being billiard ball-like objects -- utterly fails in the quantum world. It turns out that the correct classical limit for quantum fields in many situations is classical fields rather than point particles, and so you must solve the field equations for a field with imaginary mass and see what happens rather than just naively assume the velocity will turn out to be faster than light.
The mathematical details are a bit technical so I'll just refer to Baez's excellent page if you're interested ( http://math.ucr.edu/home/baez/physics/ParticleAndNuclear/tachyons.html ), but the conclusion can be stated very simply. There's two types of "disturbances" you can make in a tachyon field:
1) Nonlocal disturbances which can be poetically termed "faster than light" but which do not really represent faster than light propagation since they are nonlocal in the first place. In other words, you can't make a nonlocal disturbance in a finite sized laboratory, send it off to your friend in the andromeda galaxy and have them read the message in less time than it would take for light to get there. No, you could at best make a nonlocal disturbance that is as big as your laboratory, and to set that up you need to send a bunch of slower than light signals first. It's akin to telling all your friends all over the solar system to jump at exactly 12:00 am tomorrow: you'll see a nonlocal "disturbance" which cannot be used to send any information because you had to set it up beforehand.
2) Localized disturbances which travel slower than light. These are the only types of disturbances that could be used to send a message using the tachyon field, and they respect special relativity.
In particle physics the term "tachyon" is used to talk about unstable vacuum states. If you find a tachyon in the spectrum of your theory it means you're not sitting on the true vacuum, and that the theory is trying to "roll off" to a state of lower energy. This actual physical process is termed tachyon condensation and likely happened in the early universe when the electroweak theory was trying to find its ground state before the Higgs field acquired its present day value.
A good way to think about tachyons is to imagine hanging several pendulums on a clothesline, one after the other. If you disturb one of them, some amount of force will be transmitted from one pendulum to the next and you'll see a traveling disturbance on the clothesline. You'll be able to identify a "speed of light" for this system (which will really be the speed of sound in the string). Now you can make a "tachyon" in this system by flipping all the pendulums upside down: they'll be in a very unstable position, but that's precisely what a tachyon represents. Nevertheless, there's absolutely no way that you could send a signal down the clothesline faster than the "speed of light" in the system, even with this instability.
tl;dr: Careful consideration of tachyons makes them considerably different from science fiction expectations.
EDIT: As per jdlugosz's suggestion, I've included the link to Lenny Susskind's explanation.
http://youtu.be/gCyImLu0HSI?t=58m51s
Best Answer
Yes, if a particle would be travelling faster than light, it would always travel faster than light. This is what's called a tachyon, and they have in some sense imaginary mass.
The three regimes, time-like, light-like and space-like (i.e. subluminal, luminal and superluminal space-time distances) are invariant under Lorentz transformation. Therefore anything on a super-luminal 'mass-shell' would always stay there and could not be decelerated to light/ or sub-light speed.
The problem is not that it would violate relativity, but rather causality, since with faster than light information propagation one could 'travel back in time', therefore leading to paradoxes.
For an introduction check out Wikipedia