Código PHP:
int numeros [][]=new int [4][4], ocupados=0, numero=1, x1=0, y1=0, x2=0, y2=0;
while (ocupados !=16)
{
x1 = (int) (Math.random() * 4)-1; //posicion aleatroria "x" del primer numero
y1 = (int) (Math.random() * 4)-1; //posicion aleatroria "y" del primer numero
x2 = (int) (Math.random() * 4)-1; //posicion aleatroria "x" del segundo numero
y2 = (int) (Math.random() * 4)-1; //posicion aleatroria "y" del segundo numero
if(numeros[x1][y1]!=null && numeros[x2][y2]!=null) //si las 2 posiciones estan vacias metes el numero en las 2
{
numeros[x1][y1]=numero;
numeros[x2][y2]=numero;
ocupados+=2; //aumentas el numero de casillas ocupadas en 2
numero++; //aumentas el numero siguiente
}
}
Ese es un metodo simple pero no esta optimizado, espero que te sirva