Some ranks in disguise, and possibly perform (to act as other than a simple commoner) would be invaluable. I second the recommendations for bluff, etc. listed by Barendd.
Also, consider that your killer doesn't necessarily have to be evil - insane or tragically deluded work just as well, and are perhaps creepier.
For example, a killer who simply hates everyone, and kills for the sheer pleasure of it is evil, and perhaps a formidable opponent, but uncomplicated, and likely easy to bait.
However, an insane killer might only appear to hate everybody, when in fact there is a very reasonable justification for his actions (at least in his mind) which the authorities never picked up on. Better yet, they ascribe the wrong "serial killer-esque" motive to him (and inform the pcs of that incorrect motive).
Consider, for example, a commoner who wants to be a paladin, and hears a voice telling him that certain people are fiends in disguise. He KNOWS that it's true, and he HAS to kill them before they do any damage. He also KNOWS he was CHOSEN by his god to do this, because that is the ONLY way his non-magical weapons could possibly have killed all these fiends. He CAN't tell anyone why he's done what he's done, because they might be fiends, too, and the risk of letting the fiends know he knows about them is too great. So what if they tortured him in a vain attempt to find out where the rest of the fiend's corpses lie? So what if he's been locked away for all this time? A paladin made to suffer for his good deeds is only made stronger by the suffering, and in seeing who fights and imprisons him, he discovers the identities of more fiends....
In his mind, that character is Lawful Good. He's just wrong in his perception of a few things. Alternatively, you could even make him correct in his perception: Add minor demon who repeatedly appears to the character as a Celestial being(Even as the character's god), telling him that he will be made a paladin if he can pass these tests, and destroys the fiends infesting the city.
Such a scenario also has the advantage that the victims he chooses after his escape will be different than those he targeted before his capture. (Before his incarceration, the paladin-to-be thought that wearing a silver ring was the mark of being a fiend. The authrorites notices that all his victims shared this characteristic, and thought that was the end of it. But the magistrate who threw him in jail wasn't wearing a ring, and HE was DEFINTELY a fiend, so now the killer has to accept that his criteria for recognizing fiends just wasn't broad enough...)
This scenario also explains why someone with such incredible stats is still a commoner - until he's accepted as a paladin, no other training is good enough for him.
Anyway, FWIW
Ian