How cold are we talking about? I find that thin uninsulated flexible shoes often keep my feet much warmer than more insulated inflexible shoes as long as I keep moving, because they require a lot more muscle use by the feet and lower legs, and blood ends up circulating more. When just sitting around they can get cold though.

You could try a knee-high leather moccasin or the like.