Found that MP4Box can do that.
Installation: sudo apt-get install gpac
Usage: Mp4BoxMP4Box -add movie.subsengsubs.srt:lang=eng movie.mp4 -out movie.subbed.mp4
It took 1 minute, 23 seconds to process an hour long movie.
Hoping it works, I'll test it tomorrow with the embedded player on my Xbox.