If the frame-rate is not too high and you can associate a frame with a precise timestamp then the easiest would be to add the metadata as textual subtitles.
The other option is to mux the metadata as standard headers in
.mp4 or similar container format.
.mp4 can be broken down into multiple fragments, each one with its own header, and theoretically this can be done per frame. However, doing that for more than a few frames is extremely inefficient in terms of file size and performance. A variation of this method would be to extract every frame as an image (e.g. JEPG), and set its metadata.
Yet another option is to use stenography without any hacking, you just encode the metadata into a separate stream which is timestamp-synced with the main video stream. Most modern container formats, including
.mp4, can accommodate multiple video streams in the same container (e.g., you can label the encoded metadata stream as the same content but in another language).