<?php
$arr = Array (
    Array("teste0", 1),
    Array("teste1", 1),
    Array("teste2", 2),
    Array("teste3", 2),
    Array("teste4", 2),
    Array("teste5", 3),
    Array("teste6", 4),
    Array("teste7", 4)
);

$contagens = Array();
foreach ($arr as $key => $subArr){
	$val = $subArr[1];
	$contagens[$val] = isset($contagens[$val]) ? $contagens[$val] + 1 : 1;
}


usort($arr, function ($a,$b) use ($contagens){
	return $contagens[$a[1]] == $contagens[$b[1]] ? $a[1] - $b[1] : $contagens[$b[1]] - $contagens[$a[1]];
});

echo "<pre>";
print_r($arr);

echo "</pre>";
?>