The browser just reads the TOC-ish stuff from the first chunk. Trust me, it works. I regularly load plain old multi-hundred-megabyte mp4s in my browser, off a web server, and skip around without problems. The default keyframe interval from x264 is fine. You don't have to do any horrible things to the encoding, you just have to start loading a few seconds before the seek point. Which the browser does automatically.

Do browsers even support embedded subtitles?