The above screenshot shows my problem. As I scroll down in vim, black lines start appearing. Please note that initially all is good, but the problem happens if I scroll down.
I've already tried searching for solutions, almost all the time I end up with gnome 256 color solution and vim t_Co, I've enabled both in the required configuration files already.
This is a bug in VTE, the terminal emulation widget behind GNOME Terminal and many other terminal emulators. Version 0.44 introduced the breakage and 0.48.3 fixes it.
See the details here, or jump straight away to the fix if you feel like patching and recompiling a particular buggy VTE version. (After installing the patched version, you'll have to close all GNOME Terminal instances at once so that the server process restarts.)
VTE would err on the side that is depicted there as the correct one. Please note that the linked bugreports mentions iterm and Terminal.app terminal emulators which have nothing to do with VTE. So even if it turns out to be buggy under VTE too, it's probably a bug in vim-airline rather than at least 3 different terminal emulators.
vim-airline looks buggy for the exact same core reason that made us change VTE (and unfortunately broke it in other ways, as seen above) at the first place, in version 0.44.