Confused About Linked Rigs & Meshes
I think I found the answer, at least for this specific situation.  It was in "How can I modify the mesh of a linked character?", but it took me a while to figure out how to make it work.  Using scene_linked-rig-skin.blend above:


The rig (char.blend) is already linked in as a group and proxied, according to instructions found elsewhere.  The group contains the rig and the mesh (and should contain any other necessary objects).  Note that the "group instance" Skin is visible but outlined in dark red (as is the rig, which is in the same group).

I linked the Skin object from the same file (appending, as mentioned in the link above, seemed to do the same thing).  The Skin is outlined in blue.  The Physics tab options are all grayed out.
 
With the Skin still selected, I did "Object... -> Make Local -> Selected Objects".  The Skin outline changed to green and the Physics options became active.  I clicked on "Collision".
 
Now the cloth simulation works!  The Skin also follows the rig (you can't see it very well since it's under the cloth).



A few interesting notes:


The skin stays with the rig, even though it's not a child of the rig (at least not according to the Outliner).  [Update] As mentioned by Jerryno below, this is due to the armature constraint.  Parenting the skin to the rig isn't necessary (I had no idea!).
This still doesn't work in my "real" scene (i.e., the one that prompted me to ask this question).  But it does if I link my "real" rig into a new file.  I suspect some data-block is stuck somewhere.
The mesh data-block is still linked (and hence not editable).  This will make the file size smaller.  It can also be made local, if desired, by choosing "Selected Objects and Data" in step 3.
It only appears to work correctly if the 3D cursor is at the origin when the rig is linked.  The rig appears where the 3D cursor is, but the skin only appears at the origin, and the offset is fixed from then on.  If you move the (localized) skin to the rig, the deformations get all wonky.  Maybe someone else has a workaround for this.
If you want to tie the cloth to the armature (e.g., for clothing), CTRL-P will parent it to the proxy of the armature, and things won't work correctly.  Since you can't select the original armature directly, you have to then edit the armature modifier and choose the original armature.