A model for a non-Kerr cylindrical nematic fiber is presented. We use the multiple scales method to show the possibility of constructing different kinds of wave packets of transverse magnetic modes propagating through the fiber. This procedure allows us to generate different hierarchies of nonlinear partial differential equations which describe the propagation of optical pulses along the fiber. We go beyond the usual weakly nonlinear limit of a Kerr medium and derive a complex modified Korteweg-de Vries equation (CM KdV) which governs the dynamics for the amplitude of the wave packet. In this derivation the dispersion, self-focussing, and diffraction in the nematic fiber are taken into account. It is shown that this CM KdV equation has two-parameter families of bright and dark complex solitons. We show analytically that under certain conditions, the bright solitons are actually double-embedded solitons. We explain why these solitons do not radiate at all, even though their wave numbers are contained in the linear spectrum of the system. We study (numerically and analytically) the stability of these solitons. Our results show that these embedded solitons are stable solutions, which is an interesting property since in most systems the embedded solitons are weakly unstable solutions. Finally, we close the paper by making comments on the advantages as well as the limitations of our approach, and on further generalizations of the model and method presented.