Contemporary galactic star formation occurs predominantly within gravitationally unstable, cold, dense molecular gas within supersonic, turbulent, magnetized giant molecular clouds (GMCs). Significantly, because the chemical evolution timescale and the turbulent eddy-turnover timescale are comparable at typical GMC conditions, molecules evolve via inherently non-equilibrium chemistry which is strongly coupled to the dynamical evolution of the cloud. Current numerical simulation techniques, which include at most three decades in length scale, can just begin to bridge the divide between the global dynamical time of supersonic turbulent GMCs, and the thermal and chemical evolution within the thin post-shock cooling layers of their background turbulence. We address this GMC astrochemical scales problem using a solution methodology, which permits both complex three-dimensional turbulent dynamics as well as accurate treatment of non-equilibrium post-shock thermodynamics and chemistry. We present the current methodology in the context of the larger scope of physical processes important in understanding the chemical evolution of GMCs, including gas-phase chemistry, dust grains and surface chemistry, and turbulent heating. We present results of a new Lagrangian verification test for supersonic turbulence. We characterize the evolution of these species according to the dimensionless local post-shock Damköhler number, which quantifies the ratio of the dynamical time in the post-shock cooling flow to the chemical reaction time of a given species. Lastly, we discuss implications of this work to the selection of GMC molecular tracers, and the zeroing of chemical clocks of GMC cores. ; Comment: 35 pages, 7 figures, 16 tables. Accepted to MNRAS. Revised to correct some typographic errors