We study gravitational collapse of low-metallicity gas clouds and the formation of protostars by three-dimensional hydrodynamic simulations. Grain growth, non-equilibrium chemistry, molecular cooling, and chemical heating are solved in a self-consistent manner for the first time. We employ the realistic initial conditions for the abundances of metal and dust, and the dust size distribution obtained from recent Population III supernova calculations. We also introduce the state-of-the-art particle splitting method based on the Voronoi tessellation and achieve an extremely high mass resolution of ~10^{-5} Msun (10 earth masses) in the central region. We follow the thermal evolution of several early clouds with various metallicities. We show that the condition for cloud fragmentation depends not only on the gas metallicity but also on the collapse timescale. In many cases, the cloud fragmentation is prevented by the chemical heating owing to molecular hydrogen formation even though dust cooling becomes effective. Meanwhile, in several cases, efficient OH and H2O cooling promotes the cloud elongation, and then cloud filamentation is driven by dust thermal emission as a precursor of eventual fragmentation. While the filament fragmentation is driven by rapid gas cooling with >10^{-5} Zsun, fragmentation occurs in a different manner by the self-gravity of a circumstellar disk with <10^{-5} Zsun. We use a semi-analytic model to estimate the number fraction of the clouds which undergo the filament fragmentation to be a several percents with 10^{-5}--10^{-4} Zsun. Overall, our simulations show a viable formation path of the recently discovered Galactic low-mass stars with extremely small metallicities.