I've normally roughed in a masonry box like Fred described, but 95% of my experience is commercial and industrial applications. Every box that I've put in a block or brick wall was held in place by the morter. I have put 4/0 (octagonal) boxes in masonry walls before, and they work fine. If you stub out a wire like Jon (who sounds as if he has much more residential experience than I do) says above, I would go a step further, and tell the brick foreman exactly where you want the box to be located in the wall. Remember, if it is wrong, that brick mason will be long gone to the next job, and they'll be asking you why the box is in the wrong spot.
Good Luck.
HMEL #688
