Well, after my own official conclusion that the back-up process was indeed stuck, I managed to solve the problem with a "ghetto-style" solution. In case anyone finds themselves in the same boat, here's what I did:
At the moment, I do not have access to the server's database, only the admin control panel. So, I can't delete the maintenance.flag file, or mess around with any other files etc. But when the site is in maintenance mode, not even the admin control panel is accessible.
Anyhow, if your back-up process within the Magento Connect control panel gets stuck - you can not cancel the process or do anything other than wait, which obviously won't help and your store will stay in maintenance mode. What I did was, before exiting the Magento Connect panel, I copied the URL leading to the Magento Connect panel from my browser. I then closed the tab, opened up a new one and pasted the said URL into the browser. The URL worked and I was able to re-log into the Magento Connect panel. This time however, I was able to tick / untick all the boxes and change all the settings etc. I unchecked the "Put the store in maintenance mode while installing extensions / creating a back-up" option, as well as the "Create a back-up" option and tried installing an extension. Low and behold, the extension installed just fine and the process stopped the maintenance mode as well. Everything works as it should now.
So, problem solved!
