Flow through partially frozen pores in granular media containing ice or gas hydrate plays an essential role in diverse phenomena including methane migration and frost heave. As freezing progresses, the frozen phase grows in the pore space and constricts flow paths so that the permeability decreases. Previous works have measured the relationship between permeability and volumetric fraction of the frozen phase, and various correlations have been proposed to predict permeability change in hydrology and the oil industry. However, predictions from different formulae can differ by orders of magnitude, causing great uncertainty in modeling results. We present a floating random walk method to approximate the porous flow field and estimate the effective permeability in isotropic granular media with specified particle size distributions, without solving for the entire flow field in the pore space. In packed spherical particles, the method compares favorably with the Kozeny-Carman formula. We further extend this method with a probabilistic interpretation of the volumetric fraction of the frozen phase, simulate the effect of freezing in irregular pores, and predict the evolution of permeability. Employing no adjustable parameters, our results can provide insight into the coupling between phase transitions and permeability change, which plays important roles in hydrate formation and dissociation, as well as in the thawing and freezing of permafrost and ice-bed coupling beneath glaciers.