Is it possible for incoming video/audio streams to contain malware through exploits in the transfer of the video/audio?
It could be possible in some cases. For example, imagine that the videoconferencing software has a vulnerability into the file format parser (E.g. buffer overflow)... then it could be exploited by a remote attacker.
Look at VLC for example http://www.cvedetails.com/vulnerability-list/vendor_id-5842/opec-1/Videolan.html
Yes, it is very possible to gain remote code execution (RCE) via programs such as Skype. For example, there was a notorious exploit in the FreePBX client provided with the Elastix 2.2 platform which triggered by merely accepting a call, as can be seen here on youtube, which gives full code exeuction.
Also looking through www.exploit-db.com shows you that technologies like Skype have used or still make use of HTTP based protocols for some of their features, which have also previously been exploited succesfully.
As for Omegle: @Wolfer already correctly identified that it uses flash which has been known to have more than its fair share of bugs that have been succesfully used to create exploits, and any future ones will no doubt also have an effect on Omegle.