Cmdr Adama doesn't have anyone else. Col Thai may be an alcoholic, Starbuck may be totally off the rails, but with 47,000 people left and a tiny fraction of them being military he doesn't have anywhere else to turn. He can't replace them and he can't live without them, especially in Starbuck's case. Even Thai, though, has training and knows things about the Galactica that aren't easily replaced or retrained.
I don't read autocrat. He is, however, Commander-in-Chief of what's left of the Colonial Fleet. He can't sit people down and ask them what they think -- no military works like that when in a tight spot. He has to make a call and then live with the consequences. On one hand, if he lets the President get away with inciting mutiny and directing the military then where does that stop? On the other hand, if he removes her from power where does he stop? He can't win, so he just chooses.
Still, your point about the religion-mad President seems correct, but neither he nor his senior officers know that nor believe that. In fact, only Gaius is in possession of any useful facts about the Cylons, aside from how to kill them, and he's looking like he's headed stark-raving-bonkers and certainly not about to offer up any information in case that leads back to "so, you're the reason that everyone's dead...".
I think his only other option would have been to go to the Quorum of Twelve and ask them to remove/denounce the President, but that opens a can of worms that he doesn't need. He doesn't know where Earth is -- he lied. Laura knows that, and now so does Starbuck. He's trapped behind a lie that he needed to tell to give people hope that they weren't just being hunted to extinction and that was all there was left. He can't tell the Quorum that he lied without losing all credibility, and he can't risk President Roselyn choosing to open that can of worms. Basically, he's not ready for the political game and he's backed into a corner by previous choices. So, it's guns or no guns. As a career military man he goes with what he knows -- guns.