The data issue can be addressed by only having videos play automatically when the user is on a wifi connection. This is the default for mobile devices already, so it's arguably already solved for most users.
The "convenience" issue is something that I strongly suspect is actually something that people think one way but act another - lots of users claim to hate auto-playing videos but then they watch them a lot. Facebook's video engagement statistics are hard to argue with - a well designed video that works without sound (eg something from Buzzfeed) gets a tremendous number of shares, likes and click through engagements.
I strongly suspect that turning off auto-playing video, even by default, would actually make the web worse for the majority of people. For those who prefer them not to autoplay, browser vendors do provide that, but the functionality is usually buried in the equivalent of chrome://flags somewhere.