MP4 supports softsubs, in the TTXT format (read more
here). Basically it can be described as XML madness. And to get a TTXT softsub you need to go from ASS/SSA (where applicable) -> SRT -> TTXT (through mp4box, or some other program if it exists...). And then you can mux it into an MP4 file, however you will only be able to see the subs if you use a splitter like Haali (AFAIK, not sure about the rest). It doesn't work with the XBOX360, as expected, and the PS3 and rest are most likely the same.
And there are no tools AFAIK for editing TTXT subs, apart from using a text editor. >_>
Ending Note: It's a rather messy format.