Make that nineteen states, I had neglected Maine. Tennessee spent a few years as the Southwest Territory. The other state that never went through the territorial stage was California. It was unorganized territory under military administration after the Mexican Cession and was admitted as State without ever being an organized territory.
Without looking at Benj's answers, I guessed Vermont, Maine, WV, and Texas, but did not think of Kentucky.
California crossed my mind, but I dismissed it because I figured that even if there wasn't a "California Territory" (which I wasn't sure of) it had to have been part of the US before it was a state in some sort of territorial capacity. Though, sure, unorganized territory straight to statehood is unique.