I go climbing about twice a week, and after a month or so my shoes are quite dirty. Not only do they smell, but I can actually see the dirt on the inside (probably from walking around barefoot on less-than-clean surfaces). I'd like to eliminate the smell at the very least and perhaps keep them generally cleaner (but I guess this involves using slippers). I've found a similar question about running shoes, but I'm not sure if the materials used in climbing shoes make any difference? I also saw that they use some kind of spray on the boots they rent at the gym, but I'm not exactly sure what.
I agree with @Dean that "the most important thing is prevention" but my method is slightly different.
Over my first 6 months of climbing ~2/wk indoors, my climbing shoes became unbearably (and embarrassingly) smelly, despite religiously air drying them after use. As OP mentioned, they were also visibly dirty on the inside. And it's worth noting that I never wear socks with my climbing shoes.
My friend (and much more experienced climber whose been through several pairs of climbing shoes over the years) insisted that I could wash them in the machine but I remained concerned about damaging the rubber and/or the glue that holds parts of the rubber together. I finally put them through a side-loading washing machine with a load of laundry. They came out smelling much better, looking clean and none the worse for wear.
After going to the gym with my newly washed shoes, I noticed some odor had returned, although nothing like before. So, while they were still moist with sweat, I put 1-2 tablespoons of baking soda in each shoe and rubbed it around the inside. Also, as noted, I allow them to air dry. Before returning to the gym a few days later, I banged the shoes together to remove excess baking soda out.
After 2-3 trips to the gym, the baking soda was no longer visible on the inside of the shoe, so I repeated the process. So far (about 1 month of 2-3 gym visits/wk) this seems to be preventing the smell from getting worse. When they again become visibly dirty, I'll either put them through the wash or try @Dean's toothbrush & vinegar method.
I had a period of serious shoe funk, and tried a number techniques before finding a system that works for me. It should be noted that shoe odor tends to be much worse in synthetic shoes.
The most important thing is prevention. Do not put your shoes in a bag, ever. Even in an open canvas bag, the shoes don't dry out as well between sessions. I've taken to always clipping my shoes onto the outside of my bag so that they're always airing out.
Even so, dirt and sweat will take its toll over time, but there are a number of ways to clean your shoes. I tried the washing machine, but it seemed a bit harsh on the rubber. My preferred method is to just hold them under the tap, run warm water and scrub the hell out of them with a toothbrush. Once the water coming out of them turns clear, I dip the toothbrush in vinegar and give them a good scrub all over to kill any bacteria. After that, I rinse them again and put them aside to dry. I've never had any odor problems survive this.
A disinfectant spray to kill fungus certainly can't hurt, but isn't as important if you're the only one using the shoes.
There are a lot of things you can do to increase the shelf life of your rock climbing shoes as well as reduce the odor/bacteria in it: