How can I cancel and replace a Transaction that never gets confirmed?
You could import the private keys used into another wallet and spend the funds there.  For instance, on Blockchain.info/wallet you simply do Advanced -> Import and import the private keys (which can be exported from Bitcoin-Qt's debug console).