Today, I found http://www.greenlayers.com/ - an ecommerce site for stock alpha videos. They provide some free samples, and I decided to see how well one works with Kdenlive 0.7.4.
Well, it did not work because I thought it was going to have a green background for chroma keying. Instead, the video contains an alpha channel, which is even better! Except, MLT's avformat producer was not prepared to handle it. It seemed like it would require little effort to make it, so I made the changes and committed them to the Git repository. Now, you can see it works beautifully!