Is it possible to get a professor position without having had any fellowships in grad school?
There's no way that you are going to be disqualified from faculty positions by not having a graduate student fellowship. There's no "has a fellowship" checkbox on rubric that search committees use. 
What will matter is a holistic evaluation of the quality of your research, your publications, your teaching experience, and your letters of recommendation.

Of course, evaluating junior faculty candidates is difficult and lots other things matter as well and can help reinforce (or cast doubt) on a committee's evaluation of a candidates quality. In that sense, a prestigious fellowship can be an additional positive signal in an otherwise strong packet. In that context, you should think of a fellowship as a "nice to have" — it does nothing to replace great research, great publications, and great letters.

In some ways, not having a fellowship might even help, if it translates into more work as a TA and RA.  This might lead to teaching experience and publications, which will be viewed as more valuable than all but the most prestigious fellowships. For example, I've seen faculty candidates who had made it entirely through graduate school on fellowships dinged for a lack of teaching experience.