I scouted several options like brick wallpapers (yuck!), real bricks (expensive), fake fiberglass bricks (also expensive)... but then, at the office I saw many old foam core boards (KAPA Line), I had salvaged from other projects.
These boards are 5mm thick with coated paper on the front and the back. One side had a print on it and as I peeled it of, it resulted in a nice rough paper surface. So that was, what I was going with.
I started by drawing some lines on the wall using a level to guide me. Then I glued the tiles on the wall using tiling adhesive. Since the tiles are very light, they stuck pretty good and didn't come off 'til the glue cured.
Using my spacers I kept adding row after row, randomly picking tiles, but tried to arrange them so they would look realistic. This took about two hours.