We report on a highly selective experimental setup for particle-$\gamma$ coincidence experiments at the Super-Enge Split-Pole Spectrograph (SE-SPS) of the John D. Fox Superconducting Linear Accelerator Laboratory at Florida State University (FSU) using fast CeBr$_3$ scintillators for $\gamma$-ray detection. Specifically, we report on the results of characterization tests for the first five CeBr$_3$ scintillation detectors of the CeBr$_3$ Array (CeBrA) with respect to energy resolution and timing characteristics. We also present results from the first particle-$\gamma$ coincidence experiments successfully performed with the CeBrA demonstrator and the FSU SE-SPS. We show that with the new setup, $\gamma$-decay branching ratios and particle-$\gamma$ angular correlations can be measured very selectively using narrow excitation energy gates, which are possible thanks to the excellent particle energy resolution of the SE-SPS. In addition, we highlight that nuclear level lifetimes in the nanoseconds regime can be determined by measuring the time difference between particle detection with the SE-SPS focal-plane scintillator and $\gamma$-ray detection with the fast CeBrA detectors. Selective excitation energy gates with the SE-SPS exclude any feeding contributions to these lifetimes.