The hadith is sahih and appears in both sahih books and other hadith compilation.
Hadith interpretation by imam an-Nawawi
In his commentary on sahih Muslim imam an-Nawawi said the following (My own translation take it carefully):
( فإذا لقيتموهم فاقتلوهم فإن في قتلهم أجرا ) هذا تصريح بوجوب قتال الخوارج والبغاة ، وهو إجماع العلماء ، قال القاضي : أجمع العلماء على أن الخوارج وأشباههم من أهل البدع والبغي متى خرجوا على الإمام وخالفوا رأي الجماعة وشقوا العصا وجب قتالهم بعد إنذارهم ، والاعتذار إليهم .
(So when you meet them, kill them, for in their killing you would get a reward ) this is a declaration of the order to fight the Khawarij and the unjust or oppressive and there's a consensus of scholars on this. al-Qadi (*) said: The scholars are in consensus that if the Khawarij or whoever resembles them from among the people of innovation and oppression go out and fight the Imam (be it a local Muslim leader or a caliph) and have diverged from the opinion jama'h and raised the club it is obligatory to fight them after warning them and asking them to ask for forgiveness.
قال الله تعالى : فقاتلوا التي تبغي حتى تفيء إلى أمر الله لكن لا يجهز على جريحهم ولا يتبع منهزمهم ، ولا يقتل أسيرهم ، ولا تباح أموالهم ،
Allah the almight said: "then fight against the one that oppresses until it returns to the ordinance of Allah. (49:9) "
But it is not allowed to give the cup de grace to their wounded, nor to follow their losers (those fighters who run away after the lost of a battle), not to kill their war prisoners, nor is their money halal (as a war booty).
وما لم يخرجوا عن الطاعة وينتصبوا للحرب لا يقاتلون ، بل يوعظون ويستتابون من بدعتهم وباطلهم ، وهذا كله ما لم يكفروا ببدعتهم ، فإن كانت بدعة مما يكفرون به جرت عليهم أحكام المرتدين ،
And as long as they didn't disobey nor prepare to fight they shouldn't be fought. But advised and given the chance for repentance (and asking forgiveness) for their innovation (Bid'ah) and their falsehood, all this applies as long as their innovation didn't turn them to disbelieve, as if their bid'ah was of the kind that turns them to disbelievers the rulings of apostasy would apply to them.
وأما البغاة الذين لا يكفرون فيرثون ويورثون ، ودمهم في حال القتال هدر ، وكذا أموالهم التي تتلف في القتال ، والأصح أنهم لا يضمنون أيضا ما أتلفوه على أهل العدل في حال القتال من نفس ومال ، وما أتلفوه في غير حال القتال من نفس ومال ضمنوه ، ولا يحل الانتفاع بشيء من دوابهم وسلاحهم في حال الحرب عندنا وعند الجمهور ، وجوزه أبو حنيفة . والله أعلم .
As for the oppressors which are not considered as disbelievers they may inherit and be inherited, and their blood in case of fight is a lost, and also their wealth if it was lost during the fight, and the most correct (view) is that they won't be considered as responsible for what the same from among the people of just (cause) (**) during the fight, but what ever they might have taken (of money or souls) out of the fight they would be considered accountable for, and it is not permissible to use (or benefit by using) any of their arms or moving creatures (camels, horses ...) during the fight is not allowed in our madhhab and the view of the majority, but abu Hanifa allowed it. And Allah knows best.
(*) I assume he refers to al-Qadi 'Iyad. (**) refers to the members of the Muslim army which is fighting the Khawarij and/or oppressors.
This makes clear that the statement of the hadith is not about hypocrites and that killing a person that says "La Ilaha illa Allah" is not allowed unless they have committed an innovation and oppress people to the extend that they might be considered as a danger for the population or as disobeying the Muslim ruler. And the decree to fight them can only be declared by an authority. Self-justice is not the intent nor the message of this hadith.
From other commentaries
Ibn Hajar when commenting this hadith in his fath al-Bary basically restricted his commentary on the Khawarij (maybe he has commented it in another part of his book more widely, but I didn't come across such a comment).
Mulla 'Ali al-Qari -in his Mirqaat al-Mafateeh sharh Mishkaat al-Masabih مرقاة المفاتيح شرح مشكاة المصابيح-added a statement of al-Khattabi I'd like to display (again my own translation take it carefully):
قال الخطابي : أجمع علماء المسلمين على أن الخوارج على ضلالتهم فرقة من فرق المسلمين ، وأجازوا مناكحتهم وأكل ذبائحهم وقبول شهادتهم ، وسئل علي رضي الله عنه فقيل أكفار هم ؟ قال : من الكفر فروا ، فقيل : أمنافقون هم ؟ قال : إن المنافقين لا يذكرون الله إلا قليلا ، وهؤلاء يذكرون الله بكرة وأصيلا ، قيل : من هم ؟ قال : قوم أصابتهم فتنة فعموا وصموا .
Al-Khattabi said: The Muslim scholars have consensus that even if the Khawarij were erroneous they still are a sect among the Muslim sects. Therefore they allowed marrying them, and eating their slaughtered animals and accepting their testimony, 'Ali may Allah be please with him was asked "Are they kuffaar (disbelievers)?" He replied, "They fled kufr (disbelief)!" So it was asked, "Are they munaafiqoon (hypocrites)?" He replied, "The munaafiqoon do not remember Allaah, except little, and they remember Allaah in the morning and the evening." So it was asked, "What are they then?" He replied, "A group of people afflicted with (a) fitnah so they are blinded and deafened (by it)."
Source of the translation of imam 'Ali's explanation about the Khawarij.
Conclusion
Nobody is allowed to kill a Muslim, even if he is a hypocrite by this hadith. There's no capital punishment in shari'a that might be applied without a clear verdict of a Muslim authority!
