Laminate flooring edging
You need a heavy duty construction adhesive.  PL, Loctite Power Grab, Liquid Nails, etc.

PL makes a trim adhesive that should work well on that brick - it sets up kind of slow but once it gets set up it will stick that trim to brick just fine.