Simulating Destructible Terrain with Brushes?

You could put decals down on the terrain. A large texture may work, but, you'll get extreme stretching depending on the size of the terrain.