In reply to stonemonkeylives:
No one gives a damn how "cuddly" you've let youself become. Just go for it*. Start on easy climbs and go for quantity rather than pushing your grades. Build up your strength and stamina. Push yourself when you feel like stopping.
You say "other than cardio"? Does that mean that you have rejected the idea of running/cycling? I hope not because whilst you are trying to build up your strength and lose weight you need to get into a regime of lots of cardio vascular workouts all the time. Again start gradually and build up to it.
And what about eating and drinking? Are you looking at what's going in? Go for a healthy diet, but don't rush it to cut back or you will just get hungry from the extra exercise, and binge.
Getting into shape and staying there doesn't just happen. You have to work at it all the time so that it becomes a way of life.
You say you have joined an ordinary gym. Have you found a personal trainer? If not, why not invest in one to advise you and keep you on the straight and narrow? It's tough and very easy to get disalusioned and depressed at apparant lack of progress. It's mental as much as physical and that's where you will benefit from an understanding trainer.
Fitness has to become a way of life, but with the increase in your climbing ability hopefully a way of life you will enjoy.
Good luck.
* Obviously if you are of a certain age and unused to hard physcal exercise it might be wise to first get your GP to give you a once over to ensure that things like your ticker are healthy!