I don't know how well I can answer this but I'll give it a shot.
In a classical string, the speed of the wave pulse is proportional to the square of the tension (if I recall correctly) ie. if you quadruple the tension, you double the velocity. So yes, there is a relation between how much you stretch a string and how fast the pulse travels. But the string is made out of relativistic particles who are bumping into each other to make the wave propagate and if those particles can't move faster than the speed of light then it's pretty clear that the pulse won't move faster than the speed of light either.
The concept of velocity for a wave isn't all that straight forward, unfortunately. Check out this applet, for example http://galileoandeinstein.physics.virginia.edu/more_stuff/Applets/sines/GroupVelocity.html
The phase velocity is the speed at which individual peaks move and this can actually be made faster than the speed of light. Unfortunately, that turns out to not be at all useful for sending information. Information is usually a pulse or any discontinuity (ie. for me to be able to send useful information, it has to be something you don't know about ahead of time) and that travels at what is called the group velocity, which is never faster than the speed of light.
There is some muddy waters about faster than the speed of light velocity when it comes tunneling. It's possible for particles to tunnel through barriers or light to travel through some materials... that might be faster than the speed of light. My roommate is doing some research in the area (we share supervisors, so he's not that far out of my own field) and from what I've talked to him it's mostly an issue of there are situations where formulas about velocity may or may not apply and people are haggling about it and putting out new formulas and no one yet knows what is what. The point is that it's not well understood.
Quantum entanglement is another way I know of that can tell you information about something faster than the speed of light but it is impossible to use for communication. It's still eerie though and bugged the hell out of Einstein (for example, see the EPR paradox).
Edit: *grumble grumble* As someone linked, group velocity can exceed the speed of light (in highly dispersive media, where it is rather poorly defined - see above me mentioning that definitions of speed can become muddy). The signal velocity never exceeds the speed of light though (and that's the speed that a discontinuity travels at). If that's not enough, I'm pretty sure I can dig up a paper with at least 3 more definitions of velocity.