Options other than the NSF for PhD level grants?

A few government fellowships come to mind:

• DoE Office of Science Graduate Student Research (SCGSR)
• DoD National Defense Science and Engineering Graduate Fellowship (NDSEG)
• DoD Science, Mathematics & Research for Transformation (SMART)

There are also many fellowships from industrial research labs that you could look into, depending on your field (Intel, IBM Research, Microsoft Research, Facebook, Nvidia, etc.)

Don't forget about:

• NIH Individual National Research Service Award (NRSA) predoctoral training fellowships

I think all the answers given so far (and several others) are included in the list at gradschools.com. Start with the list here:

• Federally funded portable fellowships

It includes DOE CSGF, NASA, DHS, CDC, NDSEG, and NIH. Almost all the fellowships listed are primarily for STEM students.

A few of these are also relevant:

• Portable Fellowships from Independent Organizations

In particular: Hertz, NPSC, and a couple of others that have more narrow eligibility requirements.