Does the Bitcoin protocol provide means to add some freely definable data to transactions such that a small transaction could actually be used to timestamp arbitrary data?
Yes, the bitcoin network can be used as a timestamping service
Here is an article about it https://www.strongcoin.com/en/blog/using_the_blockchain_as_a_trusted_timestamping_service
Here are additional instructions:
Yes, but you only get a few bytes(not sure exactly how much, i think around 30, not even near a kilobyte for sure) per transaction, so the best way to go about it would be to hash your data first and then use that instead.
Based on the links in spuder's rather brief answer and also taking care of a rare restriction:
As the Private key bitcoin wiki entry states,
any 256-bit number between 0x1 and 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141 is a valid private key
Therefore, in order to have the bitcoin network timestamp a message, one can proceed like this:
Use a 256 bit hash, usually SHA-256, as a private key⁺ that one imports into one's bitcoin wallet
Transfers a small amount of bitcoins to the corresponding address and swiftly afterwards back to your own account. Since this is a fresh bitcoin address, you might have to pay a fee for this transfer unless you can afford to wait for some time
Once the transaction back to your own account has been confirmed, publish your message and one of the two transaction ids. Everyone can now easily verify that your message's hash yields a bitcoin address that was used at the time you claim to have published your message. Be aware that since anyone with access to your message can therefore simply reconstruct also the private key, so be sure to have no funds left there!
In fact, that caveat of having to wait until you transferred the funds back to an account the private key of which is secret can be easily circumvented: Instead of a simple transaction, transfer funds to a 2-of-2 multisignature transaction that needs to be signed both by the hash "private" key and one of your truly secret private keys. Now you can leave the funds on that transaction until you want to spend the bitcoins for another purpose without having to fear someone else can spend it. However, keep in mind that currently no client seems to have any intuitive way of creating or spending multisignature transactions!
⁺ In the very rare case that hash is outside the permitted range (less than 2¹²⁸ of the 2²⁵⁶ possible values), one additionally has to do something, e.g. wrapping into the valid range via
min_val = 1 max_val = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 priv_key = ((sha256(message) - min_val) % (max_val - min_val)) + min_val