With the Swift detection of GRB090423 at z = 8.2, it was confirmed that GRBs are now detectable at (significantly) larger redshifts than AGN, and so can indeed be used as probes of the Early Universe. The proposed Energetic X-ray Imaging Survey Telescope (EXIST) mission has been designed to detect and promptly measure redshifts and both soft X-ray (0.1 - 10 keV) and simultaneous nUV-nIR (0.3 - 2.3microns) imaging and spectra for GRBs out to redshifts z ~18, which encompasses (or even exceeds) current estimates for Pop III stars that are expected to be massive and possibly GRB sources. Scaling from Swift for the ~10X greater sensitivity of EXIST, more than 100 GRBs at z >=8 may be detected and would provide direct constraints on the formation and evolution of the first stars and galaxies. For GRBs at redshifts z >= 8, with Lyman breaks at greater than 1.12microns, spectra at resolution R = 30 or R = 3000 for afterglows with AB magnitudes brighter than 24 or 20 (respectively) within ~3000sec of trigger will directly probe the Epoch of Reionization, formation of galaxies, and cosmic star formation rate. The proposed EXIST mission can probe these questions, and many others, given its unparalleled combination of sensitivity and spatial-spectral-temporal coverage and resolution. Here we provide an overview of the key science objectives for GRBs as probes of the early Universe and of extreme physics, and the mission plan and technical readiness to bring this to EXIST.