Assuming solid "red" bricks, I'd just go for your first suggestion as it's not likely you'll always hit a mortar line or the edge of a brick and you can put in more than really necessary. You could remove a small section that will be covered up to extrapolate where horizontal mortar lines are so you know your top and bottom tapcons will be at least horizontally near the middle of a row.
Obviously you'll need longer tapcons and I wouldn't use anything under 1/4" dia. I'd use washers, too, to not suck the head into the material too much.
I'm assuming moisture isn't an issue on this wall.