I'm pretty sure it is the story missions which unlock the option to liberate regions, so if you don't have the option on one yet, keep working through the story. It's a while since I played, but I think if you highlight a region on the political map it should tell you whether it is "unstable" (i.e. ready for liberation) or not.
I had that issue with one military base (I forget which). I don't know exactly why it happened, but I had to go a ways away, then return to it (from a different direction). Then the guy gave me liberation mission instead of a side mission.
Eclipsing power is, at times, not only the instrument of demons, but also of gods. Lost, but not forgotten.
Yeah, ditto, I had one base that was particularly troublesome - I'd kept failing it, and when I reloaded and came straight back to it, there'd be no liberation option. It was one in the south, by the waterside, underneath a very high bridge. As LancetJades says, going away and then coming back again seems to clear it, it's frustrating but not game-breaking.
Haha yeah, I tried a couple of different approach routes and every time I'd start getting cannoned repeatedly from one barricade or another. In the end I got through with luck only - a tank didn't appear, or wasn't manned, or something like that, so I could gain myself a foothold and work with that. I wonder if that base is special for this liberation option glitch, or if it's just more obvious because it tends to require more retries :/