I've tried climbing a few times and would do it so much more if the only place near me wasn't so expensive/such a pain to get to, cuse you public transport.
It really works for me, slightly dangerous and so involving I can't be distracted by other stuff, I just get into this head space where even though the adreanaline's flowing and my heart's racing i'm really calm, which is something i've been trying to work on.
I hold my breath for a long time when i'm thinking really hard, my psychologist would remind me to breathe, never done it while active though. Have you tried going really slowly, or stopping as soon as you realised you're holding your breath? I found Pilates to be really good in terms of breath control and body awareness, maybe that would help?