WebRTC remote video is shown as black

You may need to add

<uses-permission android:name="android.permission.RECORD_AUDIO" /><uses-permission android:name="android.permission.CAMERA" />

into your AndroidManifest.xml

I verified WebRTC works with https://download.01.org/crosswalk/releases/crosswalk/android/beta/7.36.154.12/ and https://apprtc.appspot.com/ on my Nexus 5.

Hope it works for you.

I had the same issues as you, but only for some clients, and I explored the same avenues that you did. The last thing (and probably the ultimate cause of my issues) was related to the NAT situation behind at least one of the clients. There will always be the possibility of a situation where one of the clients cannot get a hole punched in their NAT, and therefore a STUN server will not work. In these cases, you need a TURN server to relay the video to that client.

What configuration do you have for your iceServers in your peerConnection? Does it contain any TURN servers that you know to work?

You can create a free account on this site http://xirsys.com/simplewebrtc/, and follow the simple instructions on getting credentials for a TURN server on their hosting, which you can then use to test if this is the issue.

First create Peer connection and then add MediaStream to it. Only after adding mediastream to peerconnection exchange of offer,answer,candidates should be done.