Is there any problem a quantum finite state machine can do faster than a classical finite state machine? All of the quantum algorithms I've seen so far require a turing-complete quantum computer, at least as far as I can tell. Are there any quantum algorithms that require only a quantum finite automaton? If so, how does their asymptotic complexity compare to the classical versions of those algorithms?
 A: This is really an open problem. Even for the class of problems which quantum computers are known to be fast at - and Shor's algorithm in particular - there is no 'hard' proof that classical computers must be slow there. (To be clear: I do not think any serious computer scientist expects factoring to be in P, but there's no formal proof that it isn't.)
It is not clear to me what you mean by 'finite state machine'. Shor's algorithm does require a universal quantum computer, but any implementation must have finite registers and their size will determine the size of integer they can factor out. 
From what I can make out, you are asking whether there are special-purpose quantum devices that provide quantum speed-ups, compared to the best classical algorithms, for a particular problem. If that's the case, you may want to look at linear optical quantum computing implementations of the Boson Sampling problem, which is exactly in that class. Some places to look are

The Computational Complexity of Linear Optics. S Aaronson and A Arkhipov. Proceedings of the 43rd annual ACM symposium on Theory of Computing (STOC '11), pp. 333-342 . Full paper (96 pages) at arXiv:1011.3245 [quant-ph].

For a more understandable reference, try this blog entry by Aaronson.
