A spatter spray is a good suggestion.
A technique with an airbrush is to place something like a folded 'V' of paper, or small wooden spatula in the way of the flow, near the nozzle and angled toward the canvas. The paint builds up slightly on the spatula before being blown off by the airbrush. This causes larger droplets to spatter against the canvas. The effect is very similar to what you describe with the toothbrush.
We'll add it to the 'think about this' list!
AndyRage's mantra for graphics engine code:
"Sure - how hard can it be?"