https://en.wikipedia.org/wiki/Independent_city_(United_State...
Of course, Washington DC could be considered one example, although the above Wikipedia link begs to differ because DC isn't a state. However, there are a few dozen more, most of which are in Virginia.
Also, this kind of administrative definition of "city" causes weird conflicts. It's easy for a city, such as Los Angeles, to be much larger than the county it's nominally located in, such as Los Angeles county. Conceptually, it's also easy for a city to be its own county, which is a different status than "not contained in any county" -- but in practice where this is supposedly the case, the city will not actually match the county boundaries, instead being noticeably bigger or smaller.
I conclude that, in order to make the claim that cities usually have self-rule, the people who would like to make this claim adjust their definition of self-rule so that it covers the things they're already sure are cities, rather than having a definition of self-rule in mind and observing that, by apparent coincidence, most "cities" turn out to have it.
Not all places start out with those things. The rules differ by state, but generally, you need a certain population, a percentage of whom must petition the higher authorities (which you mention), and then vote as a community to create the create the infrastructure and take care of themselves.
At that point, they lose a lot of the benefits provided by those higher levels, like the county and state service providers of fire, police, and garbage disposal for example.
For example, it's not possible for a VA city or county to make something a crime, unless there's a specific law on the state level allowing them to.