Is it possible to totally reskin the admin panel with a new template? Can the control panel have a skin or theme applied without it affecting automatic updates?
You can certainly override the admin css by using https://github.com/lindseydiloreto/craft-cpcss from Double Secret Agency. It's rather nice.

Lindsey also has a Admin JS plugin too: https://github.com/lindseydiloreto/craft-cpjs

Regarding actual admin template changes and their ability to survive an update, I'll have to defer that to somebody who know's more about it than myself.