Is it possible to get a professor position without having had any fellowships in grad school? As a deferred action for early childhood arrival (DACA) student, I found out that I am not eligible for federal fellowships from the government or through the university.

Some universities allow for fellowships to DACA students if they meet in-state requirements but being a student who attended undergrad at another state, I do not qualify. (I applied to all out-of-state graduate programs)

With the DACA status, I can still apply and work as teaching assistant or research assistant to fund my Ph.D. program.

So my question would be, if I do not have any fellowships on my CV and only RA &amp; TA positions, how much would this negatively impact me when applying for assistant professor positions, if at all?

Do hiring committees ever place emphasis on whether the student had had fellowships or not? And would it be more worth it to go into a Ph.D. program in-state where I may qualify for some federal fellowships made through the school (from a funding perspective)?
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.