I don't (really) use Android Studio that much (I've got a really early version installed), but in Eclipse, a "clean project" will rip-out / delete any of the generated binaries/libraries, etc. associated with the app.
I use that feature/function before I make a copy of the workspace folder/directory since it's so much smaller (i.e., is a nice "source-only" (mostly) content) that I can archive off for my history/backup versions.
Rebuilding (I would think) simply does that: re-builds the project (but maybe with an implicit clean beforehand instead of just incrementally compiling those things that have changed?).
Cheers!