We present the study of a large sample of early-type dwarf galaxies in the Coma cluster observed with DEIMOS on the Keck II to determine their internal velocity dispersion. We focus on a subsample of 41 member dwarf elliptical galaxies for which the velocity dispersion can be reliably measured, 26 of which were studied for the first time. The magnitude range of our sample is -21 < MR < -15 mag. This paper (Paper I) focuses on the measurement of the velocity dispersion and their error estimates. The measurements were performed using penalized pixel fitting (PPXF) and using the calcium triplet absorption lines. We use Monte Carlo bootstrapping to study various sources of uncertainty in our measurements, namely statistical uncertainty, template mismatch and other systematics. We find that the main source of uncertainty is the template mismatch effect which is reduced by using templates with a range of spectral types. Combining our measurements with those from the literature, we study the Faber-Jackson relation (L∝σα) and find that the slope of the relation is α= 1.99 ± 0.14 for galaxies brighter than MR≃-16 mag. A comprehensive analysis of the results combined with the photometric properties of these galaxies is reported in Paper II.