Storing data in energy for 300 million years is trivial. We are receiving data that was sent just after the creation of the universe. We are talking billions of years, not millions, that this data has lasted. The data is so intact that we are still able to get an abundance of information from it. The only 'coding' necessary is the natural 'coding' of information and data inherent in physics and cosmology.
A powerful enough laser beam of light, encoded with data, projected from within our solar system by a strong enough source, will survive for billions of years. In fact, there is a great portion of the EM spectrum that one could use. The bit rate, however, would probably not be in bps but more like bits per hours or days. A slow minutes-long or hours-long blinking. However, once sent, there would be no way humans could have ever modified or interfered with it. It would be, as far as we are concerned with our current technology, hack-proof. No encryption necessary. It could even be sent in analog form, but there would be losses of information and error correction is complicated.
Being able to catch UP to that light in order to read it, is another thing. One would presumably have to travel FTL.
But there IS a way to get it to 'come back' to us without us going after it. Aim it at a huge galactic-sized 'mirror' or 'reflector' 150 million light years away, and read the reflected data 150 million years later. How that reflector gets there, whether it is human-made, purpose-built, a natural formation, or whatever seems to fall into the category of 'can do whatever you want for your answer'. Of course, it would have to be well timed, and aimed at where the reflector is GOING to be in 150 million years, and the return reflected signal aimed at where the solar system is going to be 300 million years later, but it would be 'stored' for 300 million years, as required. And it is well within technology levels today, given the dedication of enough resources. Absolutely nothing about it that is not within the current bounds of conventional physics thinking. The technology for receiving it is already readily available. We have plenty of telescopes and receivers that would suffice. Even SETI could pick it up.
But, well, blink and you miss it.
Addendum Edit
@dhinson919 suggested an intriguing idea. By the correct positioning of black holes, dark matter, and such, use them as a gravitational lens to focus and direct an EM signal through the universe, much like we use fiber optic cable to channel laser beams. Using space itself as a storage media, the possibilities for storage are immense.