I had an old Moto phone with an FM radio that worked without headphones, although it was stated that with headphones plugged in reception would be much better (which was true). My current phone (a Moto one too) has FM radio, and I use it.

I never had a phone without FM radio. It's one of the features I actually want in my phone.