The mechanisms governing the stellar mass assembly and star formation history of brightest cluster galaxies (BCGs) are still being debated. By means of new and archival molecular gas observations we investigate the role of dense megaparsec-scale environments in regulating the fueling of star formation in distant BCGs, through cosmic time. We observed in CO with the IRAM 30 m telescope two star-forming BCGs belonging to SpARCS clusters, namely, 3C 244.1 (z=0.4) and SDSS J161112.65+550823.5 (z=0.9), and compared their molecular gas and star formation properties with those of a compilation of similar to 100 distant cluster galaxies from the literature, including nine additional distant BCGs at z similar to 0.4-3.5. We set robust upper limits of M-H2< 1.0x10(10) M-circle dot and < 2.8x10(10) M-circle dot to their molecular gas content, respectively, and to the ratio of molecular gas to stellar mass M(H-2)/M-star less than or similar to 0.2 and depletion time tau(dep)less than or similar to 40 Myr of the two targeted BCGs. They are thus among the distant cluster galaxies with the lowest gas fractions and shortest depletion times. The majority (64%+/- 15% and 73%+/- 18%) of the 11 BCGs with observations in CO have lower M(H-2)/M-star values and tau(dep), respectively, than those estimated for main sequence galaxies. Statistical analysis also tentatively suggests that the values of M(H-2)/M-star and tau(dep) for the 11 BCGs deviates, with a significance of similar to 2 sigma, from those of the comparison sample of cluster galaxies. A morphological analysis for a subsample of seven BCGs with archival HST observations reveals that 71%+/- 17% of the BCGs are compact or show star-forming components or substructures. Our results suggest a scenario where distant star-forming BCGs assemble a significant fraction similar to 16% of their stellar mass on the relatively short timescale similar to tau(dep), while environmental mechanisms might prevent the replenishment of gas feeding the star formation. We speculate that compact components also favor the rapid exhaustion of molecular gas and ultimately help to quench the BCGs. Distant star-forming BCGs are excellent targets for ALMA and for next-generation telescopes such as the James Webb Space Telescope.