For example Salamance, if I teach I fly by level up could I get rid of fly without the move deleter?
HM moves CANNOT be replaced by another move. So basically, your stuck with it until you reach a move deleter.
Source: Using HMs.