It's necessary to distinguish between a phono preamp and a preamp with a phono stage. The former is what fewtch is talking about, and he's correct. However, some current preamps, and almost all preamps if you go back far enough, have a phono stage as part of the preamp. These preamps wouldn't need an outboard phono stage to hook up a turntable, as they would have the necessary circuitry built in. Some preamps will have both a phono stage and a decent headphone output. I've got an Adcom GFP-565 that has both. Line-level preamps, such as the Melos SHA-1, have a very good headphone output, but you'd need an outboard phono preamp to hook up your turntable. And, there are other preamps with phono stages that won't have headphone capability at all.
Note that headphone capability in a preamp is not always great. Sometimes it's just stuck in as a marketing afterthought, and will not let you get the best out of your headphones.
So, the answer to your original question is that there are no universal rules. For your options, you'd need to start with your budget, and go from there.