You could try diplomacy. Give the Civ involved a good scare (or kicking) then demand the city as the price of peace. Or try more peaceful trading if this isn't possible.
The other option is using the espionage propaganda route. Other than that, yes you have to wait for marines. I use to build 1 square island cities in SMAC, for the same reason. The AI was never able to deal with them.