You are describing one of the most frustrating parts of chicken care in the winter. I haven't found anything that I'm completely happy with.
I know you can buy electric warmers that set underneath your metal waterers, but I've never had any I have some plastic electric waterers that I don't like, and often end up rotating between frozen waterers and thawed ones in the house. One year, I made my own heating platforms for underneath the waterers, using parts of a lamp kit in a metal tin (The Chicken Chick describes a similar one in her book), but sometimes, it's just too darned cold here for anything to work all the time.
Good luck. I hope someone is more helpful than I am.