Couldn'tI couldn't find any use of the phrase earlier than the 1840 Money Diggers reference, but I did find some background to which the saying might refer. Apparently the debate on cat-skinning boiled down to whether onor not it was done while the cat was still alive. Here's a clip from the disturbing House of Commons' Minutes of Evidence Taken Before Committee on Bill for Prevention of Cruelty to Animals, 1832:
And here's confirmation from The Leisure Hour, 1879, that cats were used for womens' furs, but with a denial they were ever skinned alive:
So, to answer your second question, yes, it was always quite gruesome.