ChangeSkin only needs to know the minecraft username and uuid.
I found the following sites:
Yes it have to be signed by Mojang, but we can request any skin that is currently used by a player using the uuid.
Yes it's also possible to use old skins, but the skin have to be downloaded at the time the skin was used by a player.
As far as I know no skins are deleted by Mojang, but there is no way to get the signature after someone changed it. So once downloaded we can use it forever.
Moreover Mojang added a API to upload skins. So it could be possible to let the plugin upload new skins to Mojang. Downloaded the new signed skin and then revert it. This is what a lot of minecraft heads websites did.
No you can choose any skin. For example I as games647 can choose a Notch skin.