I think your first strategy, giving counter-example, is a good start; you may have more success by giving counter-examples that carry meaning and relate to things the students already know. In the case at hand, you can also try to make the point that limits are not about arithmetic, but about asymptotic behavior.
I will consider the first fallacy you mention for illustration.
To give counter-examples that carry meaning, you can draw two graphs of functions, and have the student guess what their limits are (which you have taken to be $+\infty$). Then point (ask him or her to show you) on the graph the difference between the two functions: it is represented by the vertical space between the two graphs. Now you can draw examples where both functions go to $+\infty$, but the gap between them goes to zero, or $+\infty$, or any given number, or does not have a limit. Then you can ask (or explain how) to turn these drawings into precise counter examples. Hopefully, symbols will start to carry a meaning in the students mind rather than being purely abstract. One of the thing we teachers too often forget to tell to our students is the process that made us propose a counter example. We are like magicians pulling a rabbit out of our hat, while our true goal is to attract their attention to the trick. By the way, I prefer by far to use hand drawn graphs, because a computer generated graph needs you to think of the formula first, feed it to the computer, and then observe. What we really do is to think of the general form of the graph, and then come up with a formula. Also, students are far more likely to feel they can use this methods of reasoning themselves with hand drawn graphs than with a computer, hand you want them to be able to debunk their next fallacies themselves.
To relate the fallacies with things they already know, you can ask them if it is true that when two (positive) functions go to $+\infty$, their quotient goes to $1$. They may know that the answer is negative, and you can start get them to explain it to you (to themselves, really). Then the refreshment can be used in the case at hand, which is in fact awfully close.
To make the point that limits are not about arithmetic, but about asymptotic behavior, you can try to separate two things: the meaning of the limit (what is the behavior of the function in a certain point or direction?) and the tools to determine limits. I guess that student often confuse the two (in a wide array of topics, not only limits; as an example, many student end up considering eigenvalues as being defined as the roots of the characteristic polynomial, leaving them unable to prove that the vector with all entries $1$ is an eigenvector of the matrix with all entries $1$: I have had almost all of my students failing this question because they wanted to compute the characteristic polynomial first).
You can thus try to rephrase the first fallacy: "if two functions go to $+\infty$ as the argument goes to $+\infty$, then the gap between the two must go to zero". They may realize they have no reason to believe that (but the drawings above may be necessary to do that). Relate to the true fact that when the common limit is not $+\infty$ but a real number, then the difference must go to zero. Have them understand that the use of arithmetic is made possible then because in this situation, the conclusion is inevitable. Even if they don't have the tools to prove it, they can see it. There you are at the root of the problem (they applied a rule they learned in a situation it does not apply to, without seeing that there is a missing hypothesis; such reasoning by similarity is very common). Once they realize the difference between the two situations (finite and infinite common limit), they may accept to at least doubt what they first said. The confusion might have been entrenched in their mind because they have seen the cases when one of the two functions goes to $\infty$ and the other has a finite limit, so make them look at this case two (without formulas at first, just graphs).