Ok, se puede sin AJAX, creo que te entendi mal.
Código PHP:
// Primero obtenemos la página a mostrar, si no está definida, será la #1
$pag = (isset($_GET['pag'])) ? intval($_GET['pag']) : 1;
$filas = $4;
$celdas = $5;
$porpag = $filas * $celdas;
// Calculamos el total de páginas disponibles, suponiendo que ya cargaste los registros
$total = count($registros);
$maxpag = intval($total / $porpag);
if($maxpag * $porpag) < $total)
$maxpag ++;
// Validamos la página actual
if($pag < 1)
$pag = 1;
else if($pag > $maxpag)
$pag = $maxpag;
// Aquí muestras tus registros
$elemento = ($pag * $porpag) - $porpag;
for($lin = 1; $lin <= $filas; $lin++) {
for($col = 1; $col <= $celdas; $i++) {
if(isset($registros[$elemento]) {
// Aquí muestras tu celda actual
} else {
// Celda vacía, por si estás usando tablas
}
$elemento++;
}
}
// Paginación
$link = 'clientes.php?pag=';
echo "Páginas: ";
for($i = 1; $i <= $maxpag; $i++)
echo "[<a href=\"$link$i\">$i</a>]";
Sólo te quedaría adaptarlo a tus necesidades y verificar bien todo el HTML generado.