A city isn't the same as an HQ. You need an HQ facility, which varies depending on faction type, and the details of which can be found on the faction rules. It can be located in any city, anywhere on the galactic map, so you can buy one from someone else who happens to have one, for example.
As for city creation, anyone can found a city on a planet without a planetary government (any planet with either no flats on it, or where no faction owns a majority of flats). If you want to found a city on a planet already controlled by a faction, you can submit a request, and they can either grant approval or reject it. As such it is best to contact the faction in question prior to submitting a build request. But, as stated above, you do not need to have a city to start a faction - just a single (powered) facility.