What version-control system is most trivial to set up and use for toy projects?

I teach the third required intro course in a CS department. One of my homework assignments asks students to speed up code they have written for a previous assignment. Factor-of-ten speedups are routine; factors of 100 or 1000 are not unheard of. (For a factor of 1000 speedup you have to have made rookie mistakes with malloc().)

Programs are improved by a sequence is small changes. I ask students to record and describe each change and the resulting improvement.

While you're improving a program it is also possible to break it. Wouldn't it be nice to back out?

You can see where I'm going with this: my students would benefit enormously from version control. But there are some caveats:

Our computing environment is locked down. Anything that depends on a central repository is suspect.
Our students are incredibly overloaded. Not just classes but jobs, sports, music, you name it. For them to use a new tool it has to be incredibly easy and have obvious benefits.
Our students do most work in pairs. Getting bits back and forth between accounts is problematic. Could this problem also be solved by distributed version control?
Complexity is the enemy. I know setting up a CVS repository is too baffling---I myself still have trouble because I only do it once a year. I'm told SVN is even harder.

Here are my comments on existing systems:

I think central version control (CVS or SVN) is ruled out because our students don't have the administrative privileges needed to make a repository that they can share with one other student. (We are stuck with Unix file permissions.) Also, setup on CVS or SVN is too hard.
darcs is way easy to set up, but it's not obvious how you share things. darcs send (to send patches by email) seems promising but it's not clear how to set it up.
The introductory documentation for git is not for beginners. Like CVS setup, it's something I myself have trouble with.

I'm soliciting suggestions for what source-control to use with beginning students. I suspect we can find resources to put a thin veneer over an existing system and to simplify existing documentation. We probably don't have resources to write new documentation.

So, what's really easy to setup, commit, revert, and share changes with a partner but does not have to be easy to merge or to work at scale?

A key constraint is that programming pairs have to be able to share work with each other and only each other, and pairs change every week. Our infrastructure is Linux, Solaris, and Windows with a netapp filer. I doubt my IT staff wants to create a Unix group for each pair of students. Is there an easier solution I've overlooked?

(Thanks for the accepted answer, which beats the others on account of its excellent reference to Git Magic as well as the helpful comments.)

Solution

I would say something like Git might fit the bill:

As it's a distributed system, you don't need to have a central repository, the repos exist with the source directory
It is easy to create patch files that can be mailed and applied.
Although it might seem that git is difficult to use, the basic ideas of committing, merging, adding and removing files are not that hard to learn.

Have a look at this site Git Magic or, even this tip site GitReady