If it has 0 confirmations, I believe you can use Pywallet to remove the transaction.
Wouldn't you cause a double spend if you tried to spend the coins after this?
Which, now that I think about it, would cause both to be rejected by the network and the coins to be returned?
No double spend attempts don't cause coins to be returned.
However if you delete a transaction then your node will stop broadcasting it. Eventually all nodes delete the oldest transactions so without continual rebroadcast the tx will simply cease to exist. At that point you can create a new transaction.
Understand this is a hack and in the future you should follow network rules. The default client won't allow you to send a tx which requires a fee without a fee for this specific reason.
Thank you.