The Type~Ia supernova (SN~Ia) 2016coj in NGC 4125 (redshift $z=0.004523$) was discovered by the Lick Observatory Supernova Search 4.9 days after the fitted first-light time (FFLT; 11.1 days before $B$-band maximum). Our first detection (pre-discovery) is merely $0.6\pm0.5$ day after the FFLT, making SN 2016coj one of the earliest known detections of a SN Ia. A spectrum was taken only 3.7 hr after discovery (5.0 days after the FFLT) and classified as a normal SN Ia. We performed high-quality photometry, low- and high-resolution spectroscopy, and spectropolarimetry, finding that SN 2016coj is a spectroscopically normal SN Ia, but with a high velocity of \ion{Si}{2} $\lambda$6355 ($\sim 12,600$\,\kms\ around peak brightness). The \ion{Si}{2} $\lambda$6355 velocity evolution can be well fit by a broken-power-law function for up to a month after the FFLT. SN 2016coj has a normal peak luminosity ($M_B \approx -18.9 \pm 0.2$ mag), and it reaches a $B$-band maximum \about16.0~d after the FFLT. We estimate there to be low host-galaxy extinction based on the absence of Na~I~D absorption lines in our low- and high-resolution spectra. The spectropolarimetric data exhibit weak polarization in the continuum, but the \ion{Si}{2} line polarization is quite strong ($\sim 0.9\% \pm 0.1\%$) at peak brightness.