If you write a thesis, you might be able to use thesis committee members as recommenders- though if you start the thesis in your senior year it might be a little late to start developing a relationship. I'm having a similar problem- I'm in my first year of grad school and applying for fellowships now, and I'm not sure how to develop relationships with faculty quickly so that I can ask them for recommendation letters. In certain classes (most) I don't develop the kind of relationship with the professor where I'd want them to write me a letter- sometimes I need to ask questions (about assignments, for ex) that reflect badly on me. For undergrad I ended up asking a professor I didn't do research with to write me a letter- I took 2 classes with him, one of which involved having meetings with him about presentations/a small research project. Otherwise, I asked professors whose labs I worked in- for 1 of them I mostly interacted with an older student in the lab, but I still met with the professor at lab meetings, and later when I started my own research project. If you are doing research, go to lab meetings and ask the head of the lab if you can do some independent work, so s/he will get to know you.
Also, a letter from a postdoc could be good- a postdoc wrote one of my letters (but s/he was also my instructor for some classes).