There are a few things wrong with both your examples, but the short answer is yes - you can sometimes omit the verb "do" from a correctly worded sentence.
Firstly, the correct expression is "I do believe" (not "Do I believe" - that would be a question). It is a slightly formal way of saying "I understand that...". "I believe", or "I understand" work just as well without "do".
Saying "You enjoyed your holiday, I believe" could also be said as "I believe you enjoyed your holiday". If the sentence doesn't make sense one way, the other must be wrong.
However, you seem to be trying to say that you don't believe what has been said. Your examples are not really the most idiomatic way of saying this.
I would say:
I do not believe a word that comes out of your mouth.
That sentence would be ungrammatical without the verb "do", so there is no way you can omit it if you were to switch it around. You would have to say:
Not a word that comes out of your mouth do I believe.
However, this isn't particularly idiomatic. It sounds a little formal, almost archaic. I wouldn't use it, but if I did, it shouldn't have a comma like your example because this is all one clause - the "not" at the beginning of the sentence is negating the verb "do".