Just wondering about the following example :
I broadcast a transaction, sending X coins to some address.
Doesn't get included in blocks for a while because I don't include a fee.
Do I have a way to cancel it and broadcast it again with a fee this time ?
Yes, although I don't think the canceled transaction protocol is necessarily complete in terms of its current implementation.
See also:
http://www.bitcoin.org/wiki/doku.php?id=bitcoins_draft_spec_0_0_1#txThe "version" field allows somebody to send out a new transaction that effectively replaces an existing transaction with perhaps some new data. As long as the transaction hasn't been accepted into a block, in theory you can "recall" the transaction and modify the transaction in any way. Like I said, this is incomplete and the exact protocol to pull that off hasn't been included into Bitcoin yet. But it certainly is a possibility and may be a feature in a future version of Bitcoin.
Certainly the ability to "recall" a transaction hasn't been implemented yet in the UI, and once the transaction has been accepted into a block the only hope to really kill a transaction after that is to hope that the block doesn't get accepted into the main block chain. Then again, if the transaction has been accepted into a block without fees it shouldn't be a problem in terms of recalling the transaction for adding fees either as the issue is moot at that point.