For a proof of existence, you do not actually need to store the data in the blockchain. Merely commiting to it, by using its hash in way that is later provably used, is enough.
One such way is using a mechanism originally described as pay-to-contract.
Warning: elliptic curve math follows.
You start with any public key X (yours or someone elses). Then construct the modified key X' = (X + H(X || C)*G) [with H a hash function, || concatenation, and G the secp256k1 generator point], and send a transaction (possibly as part of an actual need to send money to X) to the address corresponding to X'. The receiver (which can be yourself if you do this for a change output) will need to add the value H(X || C) to his private key corresponding to X, to be able to spend the coins.
However, revealing X and C, plus the transaction in the blockchain you used to send to X', is a proof that C was actually known at the time of the transaction.
This scheme has the advantage of not requiring any data in the chain more than the transaction would already consume, and additionally that it is indistinguishable from a normal transaction, making it harder to censor or be subject to changing policy of nodes on the network.
An alternative possibly exists which works without modified addresses of transaction, but is not well studied yet.
