If you do not perform single line regex / highlight, your suggested strategy may not work. For example, you probably cannot determine if you have a multi-line comment without scanning multiple lines. :-)
If you have not done so already, use Traceview to determine where the slowdown is occurring. Perhaps you can optimize other things as well. For example, you might be compiling all your Pattern objects on the fly, rather than statically defining them.
Other than that, I think a typical pattern is to apply syntax highlighting only when the user pauses. One possible way to implement this could be:
Step # 1: each time you change the text (which you have already supposedly connected), postDelayed() a Runnable and save the timestamp obtained from SystemClock.uptimeMillis() in the data element of your EditText subclass (or anywhere else) you have a syntax coloring) . For the purpose of this answer, I will name your delay period that you use with postDelayed() as DELAY .
Step # 2: Runnable compares the current time with SystemClock.uptimeMillis() with the time the text was last modified. If the time difference is less than DELAY , you know that the user typed something in between when this Runnable was planned and now, so you just do nothing. If the time difference is> = DELAY , you will go through your syntax coloring.
Thus, you skip the application of syntax coloring until the user stops, thereby interrupting their input. You can tune DELAY , or perhaps tune it.
By the way, you plan to release this as an open source library, right ?:-)