In the video you can see Maduro, Venezuela's President, making the official decision public. Of course, it's still to be seen if Snowden decides to go there, and how\when is he going to do it.
I just plotted a path from Moscow to Venezuela that avoids non-Russian/Venezuelan airspace. It's less than 12,000km. Several modern Boeing and Airbus planes can do that non-stop.
I doubt it's the shortest possible. I bypassed the Lesser Antilles rather than ensure I was in international airspace trying to go between them.