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 &amp; 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.)