You will first meet a bandit on level two, "Red Meat". You will be introduced to them shortly after exiting the meat freezers. There is only one way to earn this achievement without pure frustration. As you enter the area you will see one of the cowboys duck behind a barrel. Run up behind him and shoot him in the back so he stumbles. While he stumbles you can run up to him and press to perform the melee attack from behind.
If you try to sneak up behind a bandit and punch him, he will always be facing you when the animation starts. Bandits rarely stumble so using the above technique and the information explained in the video are the only easy ways to complete this task.