Habit changing can be hard, and even harder when there is a highly addictive substance involved. I wish you the best with it.
Chewing gum may help, it at least fools parts of the brain that you are doing something with your mouth, I know it helps bodybuilder who are really craving for food when dieting for competition.
If you are using a substitute I think you should treat it like medicine and not be sloppy or intermittant with the dosage, then slowly and systematically reduce the dosage over a long enough time.
Other than that with trying to change any habit you need to always keep it in your mind what you are working towards (ie keep a vigilance) and try to avoid other people who have the habit (ie avoid social reinforcement of the habit) and associate with people who don't have the habit (social reinforcement of the right type).