We present Gemini-North K-band spectra of two representative members of the class of high-redshift quasars with exceptionally weak rest-frame ultraviolet emission lines (WLQs), SDSS J114153.34+021924.3 at z=3.55 and SDSS J123743.08+630144.9 at z=3.49. In both sources we detect an unusually weak broad H_beta line and we place tight upper limits on the strengths of their [O III] lines. Virial, H_beta-based black-hole mass determinations indicate normalized accretion rates of L/L_Edd=0.4 for these sources, which is well within the range observed for typical quasars with similar luminosities and redshifts. We also present high-quality XMM-Newton imaging spectroscopy of SDSS J114153.34+021924.3 and find a hard-X-ray photon index of Gamma=1.91^{+0.24}_{-0.22} which supports the virial L/L_Edd determination in this source. Our results suggest that the weakness of the broad-emission lines in WLQs is not a consequence of an extreme continuum-emission source but instead due to abnormal broad-emission line region properties.