With a single texture and without wasting a bunch of performance modifying/filtering it on the fly? How exactly? Would make a great addition to this discussion :)
I wonder if having a single texture and randomly rotation it with blending the edges on a square grid would look just as good or not. The texture would just have to be larger than the tile it covers