Popular folklore has it that this phrase dates back to 9th century Ireland. Viking raiders would demand tribute from the local Irish and slit open the noses of anyone who refused to pay. I do not know whether not Vikings were among the first to practice rhinoplasty, but it is most definitely not the origin of the phrase, which doesn't make its appearance until 1672. Eight hundred years of an underground existence is just too long to be plausible.
"There is another 17th century slang term for money, rhino. In Greek, of course, rhino means nose. It seems logical that these two are connected, but what significance a nose has with money is simply not known."
(Also from Dave Wilton's etymology pages.)