To get the Butcher:
Make sure you DO NOT sell the original Bronze Bangle that Cloud has equiped at the beginning of the game. Leave it on him until you sell all of the other ones you have, because you MUST have that exact Bronze Bangle
You must have Barret in your party whenever possible.
Also, you CANNOT buy ANY Chocobo Stables.
Fight the Lost Number Directly after meeting Sephiroth in the Shinra Mansion, when he gives you the Destruct Materia. DO NOT get Vincent afterward. Leave the door locked.
Right before you fight Hojo, put the Buster sword and the bronze bangle you saved from the beginning back on Cloud. Fight Hojo with these equipped, and then once you are on disk three, go to the Shinra Mansion (Cloud must still be wearing the bronze bangle and the Buster Sword) and open the coffin Vincent is found in. Instead of Vincent, the Butcher will pop out.
The Butcher hates Chocobos, and will chop them up whenever he sees them. Take him to the Chocobo farm, it's pretty funny!