Can a Markov Algorithm Replace the Empty String?
Rules of the form $\epsilon \to w$ are allowed for Markov Algorithms. Be aware, however, that they will not only match, when the string is empty. Instead they will match every string, since every string contanins $\epsilon$ as a substring.

Since a rule that matches at multiple positions will be applied to the leftmost of them by definition, Rule 3 from your question will prepend a 0 to the string and terminate, whenever no rule before it is applicable. So, unless your previous processing relies on the fact that the algorithm will terminate when no rule is applicable (or already contains a rule for a or b), adding the three rules from the question as the last rules will give you the desired result.