International students may have to do a little more work to find a program, but there are plenty out there. The programs below accept international students.
Of course, check out Randolph College's Program, and check out all the links at the page that brought you here.
Physics students should check the nucleus web site for more programs (http://www.the-nucleus.org/research/browse.cfm). Some programs may not explicitly say "for US citizens and residents". Students should always e-mail them and ask. Even programs which are funded by NSF usually have limited university funds that can support international students (check out the NSF REU site at the page that brought you here).
A physics research program at Lehigh University:
http://www.lehigh.edu/~inreu/reu/index.html
An astrophysics program at Baylor University:
http://www.baylor.edu/casper/index.php?id=20535
Students work in teams on industrial projects at UCLA:
http://www.ipam.ucla.edu/programs/rips2008/
Only for women. Research internship at IBM:
http://www.aps.org/programs/women/scholarships/ibm/index.cfm
Research Internships in Science and Engineering - Germany
KState accepts international students