Yes, it could be done on the Arduino.
You could implement a bit banging USB 1.1 in software, add in a USB Communications Device Class driver, then add in the Bus Piratey stuff.
You'd just need a small USB adapter board with the connector and passives.
It's definitely possible and it would have massive hack value. But, I suspect that you'd quickly run out of resources on the standard Arduinos to do anything useful with it.
For example, USBasp (USBasp - USB programmer for Atmel AVR controllers - fischl.de) is an AVR programmer implemented similarly (no CDC) and I doubt it's got room for much more.
V-USB (http://www.obdev.at/products/vusb/index.html) is a GPL licensed soft USB stack for AVR which will get you most of the way there...