You might benefit from some deliberate practice. Take 15 or 20 minutes out of every day to give a "lecture" to an empty room (or a room with a colleague who can critique you). During that "lecture", pick some particular aspect of your board work to concentrate on (for example, writing larger, writing slower, keeping your lines straight, &c.—you might even just practice writing particular mathematical symbols over and over again if your concern is having to erase; I once spent an afternoon practicing nothing but circles for a trigonometry class).
Part of the problem with trying to practice these skills while teaching is that you are "on the spot." If you make a mistake or write in a way that you dislike, it is easy to get flustered. Once you mess up once, you are on edge, and far more likely to mess up again. Personally, when I make a mistake, I often start moving a lot faster, too (this is a reaction to stress, I'm sure). This makes it very hard to practice your pacing while in front of a live group of students. Take the pressure off, and practice in some other setting.
Other bits and bobbles of general advice:
- Write larger. This not only forces you to slow down a little, but also makes your writing easier to see from the back of the room.
- Write in block letters. That is, pick a handwriting "font" that consists only of capital letters which are well separated from each other (though lowercase letters will necessarily show up for mathematical symbols). These letters typically take a little more care to write, but are easier to read.
- Write in narrower columns. This might seem like a silly piece of advice, but I find that it helps. When I watch other people lecture, they typically divide the whiteboard in half (roughly), and write a column of text on each half. Because they can't quite reach the right-hand side of the column from the left-hand side, they end up moving back and forth a lot, or writing slanty-wise, or otherwise messing up their board work. Divide the board into three columns. Maybe even draw vertical lines on the board before you do anything else. It will probably make your life easier.
- Keep an eraser in your off hand. I know that the question is about avoiding the use of an eraser, but... meh. Typically, no matter how slowly you write, you will be ahead of your students. Moreover, it is very difficult to write in a way that is visible to the students while you are writing. If you write something that you don't like, it is very easy to quickly erase it and correct it before the students even notice. Don't be afraid of making quick corrections.
- Mentally separate notes from exposition. You should not be trying to write down everything you say, and your students should not be copying down your words verbatim. For example, if I am relating a theorem to students, I might write four words (i.e. state a hypothesis), then spend a minute or two explaining those four words. If a theorem has a lot of hypotheses, it might take five or ten minutes just to write down a statement of the theorem. The whole statement might take up only a couple of lines, but there will have been a lot of exposition between the lines. At the end of the day, the students need a copy of the statement of the theorem in their notes, and they need to be cognizant of some motivation and explanation (but this doesn't need to be written). I have seen folk try to write down all of this exposition. Don't do that.
