I think I already used the TM dig the guy at Fossil maniac's house and replaced it with something different. I have visited the Move tutor, but dig wasn't there. I want to catch Regirock, Registeel and Regice. Do I have a chance?
Sadly, you cannot remember TM moves from the Move Relearner. Your best bet is one of the following Pokémon, who learn Dig via level-up:
These are the only three Pokémon in Gen III to learn Dig naturally.