How about a UDF. Put =FancyRand() in each of the cells. It will take a bit to settle down, but I think it will do what you want. You may want to set Calculation to manual.

Function fancyRand(Optional ByVal inRay As Range) As Double
Dim Neighbors As Range, badVal As Boolean, oneCell As Range
If inRay Is Nothing Then Set inRay = Application.Caller
With inRay
    Set Neighbors = Application.Union(.Offset(1, 0), .Offset(1, 1), .Offset(0, 1))
    If inRay.Column > 1 Then
        Set Neighbors = Application.Union(Neighbors, .Offset(0, -1), .Offset(1, -1))
        If 1 < .Row Then
            Set Neighbors = Application.Union(Neighbors, .Offset(-1, -1), .Offset(-1, 0), .Offset(-1, 1))
        End If
    ElseIf 1 < .Row Then
        Set Neighbors = Application.Union(Neighbors, .Offset(-1, 0), .Offset(-1, 1))
    End If
End With
Randomize
fancyRand = Int(90 * Rnd()) + 10
For Each oneCell In Neighbors
    badVal = badVal Or (oneCell.Value = fancyRand)
Next oneCell
If badVal Then fancyRand = fancyRand(inRay)
End Function