Perl (on *nix), 7169 bytes
The \x1bs are literal escape characters.
Relies on stty command and works well on OS X.
{printf"\e[%i;%iH\e[48;5;%imprintf"\x1b[%i;%iH\x1b[48;5;%im ",map{rand$_}`stty size`=~/\d+/g,256;redo} Similar to other approaches, but I liked the combination of all params into one call to printf so thought I'd share. Kills my terminal.
Twice as many pixels, 83 bytes
{printf"\e[%i;%iH\e[48;5;%i;38;5;%im▄"printf"\x1b[%i;%iH\x1b[48;5;%i;38;5;%im▄",map{rand$_}`stty size`=~/\d+/g,256,256;redo} This approach uses a unicode block ▄ and a random foreground and background colour which gives a more square pixel. Kills my terminal too, but looks cooler.

