I finally managed to get GDB working with Lazarus on my Mac running El Capitan (10.11.5)
The process (Without details, I don't have time right now, will write a blog post asap):
Installing GDB 8.0 (Not 8.1), codesigning (/usr/local/Cellar/gdb/8.0/bin/gdb), restarting taskgated, starting gdb once on CLI (Or just reboot), setting up Lazarus to use the proper executable instead of the symlink (/usr/local/Cellar/gdb/8.0/bin/gdb)
And finally... it works.
Anyone who says "It just works" have never done software development on a Mac.