You'll have to check if there are Great Prophets (the only unit that can start a Religion) in the great people screen. If there's a Great Prophet to still be gained, you can always start a Religion no matter if your cities have converted to another or not.
One trick to keep in mind is that every city you have that has a Holy Site in it will convert to your Religion once you use your prophet to start it. So you can grab a Great Prophet and then just have him hang around somewhere. Then, once you have your cities up and running, and with a Holy Site in each, you can "pop" the Prophet to mass convert your empire to your Religion at once.