How to prove that 3-coloring is decidable?
It depends entirely on what level of formality you're aiming for. The informal description of an algorithm in your question is quite enough to convince me that 3-colourability is decidable. If you wanted to be a bit more formal, you could give pseudocode. If you wanted to be more formal still, you could describe a Turing machine in English. If you wanted to be even more formal, you could write down the full description of the Turing machine and prove that it really does decide 3-colourability.

Having said that, of the options I've listed, it's way more likely that there'd be an error in the description of the Turing machine or in its correctness proof! So it's not clear which proof would be the most believable.