Already possible with VobSub and 3D subtitler(already mentioned in forum)
I don't think it is doable with our MEncoder build.
I know that there are some custom builds with ASS "special tags" support so you can render more subs at same time so one can be up, another down and 3rd on left etc.
In this case you can show same subs twice for both L/R picture so you can avoid using graphical VobSub.
Never experimented with it and our MEncoder builds.
http://img532.imageshack.us/img532/6756/img4573n.jpg