I tried to do so(2 VideoViews), but only one video played. It is because of linux decoder, which may be used as single instance only(from stack trace info).
For now, to achieve multiple videos playback I try to use FFmpeg as video decoder and OpenGL for render surface. I haven't done it yet, but I think that it will be too heavy operation(play multiple videos). However, I hope this is right direction for you.
I've checked decoder issue and it seems it is linux kernel depended:
I've tested on Nexus One with 2.3.4 and 2.6.35.7-... kernel - it fails.
On second rooted Nexus One with 2.3.4 and 2.6.37.6 linux kernel - it works.
Also check this link:
http://code.google.com/p/android/issues/detail?id=17802
So, play multiple videos via VideoView possible, but not on all devices(linux kernel depended, I guess).