As a native English speaker, I personally never really thought about those implications you just described. I would use that phrase for any situation with multiple options, not just an unusual one. Maybe I’m using it wrong?
As also a native English speaker, I don't believe there's any implied unusuality in the "skinning a cat" phrase. It really is just "there's more than one way."
I don't think so. Whenever I've heard the phrase it literally means "There are multiple valid solutions for a given problem" with no further connotations beyond a bit of absurdist humour.