You can do that by adding a simple if statement. If you want every 10th line to have that you can use mod operator %.
foreach ($items as $key => $item):
if (++$i == 21) break;
if ($i == 9) {
$output .= '<div>NEW LINE </div>';
}
$output.='<div class="row-fluid"><div class="span12 block">
<div class="pull-left">
<a href="'.$item->link.'" target="_blank">'.$item->title.'</a>
</div>
<div class="pull-right">
<p class="muted">'.date("m/d/Y", $item->date).'</p>
</div>
<div class="clearfix"></div>
</div></div>';
endforeach;
echo $output;