MACtac makes a product called "RoughRAP" that's specifically made more brick/concrete walls. You have to use solvent printing, and it's got an extremely high-tack adhesive that lasts. It's a "permanent" adhesive and should last through most environments because it's made for indoor & outdoor usage.
If you have a preference to a different brand, I'm sure you can call up your supplier and ask for a comparable product by a different manufacturer. If you're looking for someone to actually do the printing and/or installation for you, you might try calling around to some of the other printing shops near you and seeing if they have any experience working with this application or material.
Best of luck with the job
Sign-Man!
P.S. You didn't happen to see the Santa Surfing out in Cocoa Beach did you? It was in the Florida Today on the home page. I grew up there and was home for the x-mas break to see it; very cool!