I'd start with a small masonry bit, sized for my microphone element...
Well... my knowledge/experience is a bit dated.(used to work in
surveillance year back.)
But will share what I know.
The do make variuos "Big Ear" microphone rigs that consist of a
variable electret mike and amplifier with closed air headphones.
I've seen some stick those up to a wall with some success.
There are some mikes designed for this use as well.
Not legal in some states I've been told. You can do a web search for
spyshop or spystore, they'll have them for sale.
If you can dig in the wall as suggested above you can use the method
we used to use in the military years gone by.
use an iron or wood spike driven into the wall with a transducer
pickup on it fed into a amplifier rig that'll both amplify the
vibration and shift them down to the audible spectrum.
They also make spike mikes that do work on regular(drywall etc..)
walls. you might predrill and give one of those a try.(you;ll have to
judge the thickness of the cinderblock or concrete and under drill
just a 1/16 or so to avoid detection.)