A simple solution is to apply a random shift smaller than the margin:

function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1) + min);
}
function rand() {
    return getRandomInt(-20, 20);
}

$('li').each(function() {
    $(this).css({
        'position': 'relative',
        'left': rand() + 'px',
        'top': rand() + 'px',
    });
});

Fiddle

A more complete solution is to calculate and add the width of the elements, distributing them in rows according to the average of the widths. Then, in each line, the elements are distributed as if it were a table independent of the other lines.

I do not know if I can explain the algorithm well, so I'll post the code:

function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1) + min);
}
function rand(n) {
    return getRandomInt(-n, n);
}

//calcula tamanhos dos itens para distribuição
var itens = [];
var larguraTotal = 0;
$('li').each(function(i) {
    var $this = $(this);
    larguraTotal += $this.width();
    itens.push({
        item: $this,
        width: $this.width(),
        height: $this.height()
    });
});

//define a quantidade de linhas
var linhas = Math.ceil(Math.sqrt(itens.length));
var larguraMedia = larguraTotal / linhas;

//faz a distribuição dos elementos nas linhas de uma grid imaginária
var grid = [ [] ];
grid[0].largura = 0;
for (var i = 0, larguraConsumida = 0, linha = 0, coluna = 0, proximaQuebra = larguraMedia; i < itens.length; i++) {
    var item = itens[i];

    //quebra a linha, caso mais da metade do elemento ultrapasse a média
    if (larguraConsumida + item.width / 2 > proximaQuebra) {
        linha++;
        grid[linha] = [];
        grid[linha].largura = 0;
        coluna = 0;
        larguraLinha = 0;
        proximaQuebra = larguraMedia * (linha + 1);
    } else {
        coluna++;
    }
    //armazena a largura 
    grid[linha].largura += item.width;
    larguraConsumida += item.width;
    grid[linha].push(item);

}

//coloca os elementos na posição final (uma célula do container)
var container = $('ul');
//a largura da célula (local onde o item deve ser inserido)
var larguraCelula = container.height() / grid.length;
for (var i = 0; i < grid.length; i++) {

    var linha = grid[i];
    //altura da célula (local onde o item deve ser inserido)
    var alturaCelula = container.width() / linha.length;
    //calcula o espaço horizontal que tem para randomizar, isto é, o espaço em branco até onde não enconsta no próximo elemento
    //deve dividir por 2 pela possibilidade do outro elemento também poder se aproximar, mas multiplicando por 0.4 garante que não vão encostar um no outro
    var espacoLivreEntreElementos = (container.width() - linha.largura) / linha.length * 0.4;
    //itera sobre os itens da linha    
    for (var j = 0; j < linha.length; j++) {

        var item = linha[j];
        //calcula o espaço vertical em branco para randomizar, usando o mesmo princípio anterior
        var espacoLivreVertical = (larguraCelula - item.height) * 0.4;
        item.item.css({
            position: 'absolute',
            //posiciona o item horizontalmente no meia da célula e randomiza no espaço que sobra
            left: (j + 0.5) * alturaCelula
                - item.width / 2 
                + rand(espacoLivreEntreElementos) + 'px',
            //posiciona o item verticalmente no meia da célula e randomiza no espaço que sobra
            top: (i + 0.5) * larguraCelula
                - item.height / 2 
                + rand(espacoLivreVertical) + 'px'
        });
    }
}

Fiddle

Random result 1

Randomscore2

The first thing to do is find the height and width on the screen of each word. This response in SOEN shows a possible path (create a div with the word and measure your clientWidth and clientHeight ).

var palavras = [];
var larguraTotal = 0;
var alturaMaxima = 0;
$('li').each(function() {
    palavras.push({
        elemento:this,
        largura:this.clientWidth,
        altura:this.clientHeight
    });
    larguraTotal += this.clientWidth;
    alturaMaxima = Math.max(alturaMaxima, this.clientHeight);
});

Once you've done this, you need to figure out the "harmonious" way of spreading your words on the screen (i.e. not letting them "tight" horizontally and "slack" vertically, or vice versa). One way - not necessarily the best one - would be:

var linhas = 0;
do {
    linhas++;
    var horizontal = larguraTotal / linhas / larguraConteiner;
    var vertical = linhas * alturaMaxima / alturaConteiner;
} while ( vertical < horizontal*0.8 ); // Esse 0.8 é uma "folga"

Now it's problem of the backpack ! Well, almost ... You need to choose, for each line, a set of words that approaches the desired width (% with%). I suggest starting with the larger ones, as it is easier to fit smaller ones later.

var distribuicao = [];
for ( var i = 0 ; i < linhas ; i++ )
    distribuicao.push({ palavras:[], larguraTotal:0 });
function minima() {
    var min = 0;
    for ( var i = 1 ; i < distribuicao.length ; i++ )
        if ( distribuicao[i].larguraTotal < distribuicao[min].larguraTotal )
            min = i;
    return distribuicao[min];
}

palavras.sort(function(a,b) { return b.largura - a.largura; });
for ( var i = 0 ; i < palavras.length ; i++ ) {
    var min = minima();
    min.palavras.push(palavras[i]);
    min.larguraTotal += palavras[i].largura;
}

Finally, let's distribute the words across the screen. I will do this using absolute positioning, but you can think of it in another way too.

var alturaSobrando = alturaConteiner - linhas*alturaMaxima;
var alturaAntes = alturaSobrando / linhas / 2;
for ( var i = 0 ; i < distribuicao.length ; i++ ) {
    var larguraSobrando = larguraConteiner - distribuicao[i].larguraTotal;
    var larguraAntes = larguraSobrando / distribuicao[i].palavras.length / 2;

    var top = alturaAntes + i*(2*alturaAntes + alturaMaxima);
    var left = larguraAntes;
    for ( var t = 0 ; t < distribuicao[i].palavras.length ; t++ ) {
        var palavra = distribuicao[i].palavras[t];
        $(palavra.elemento).css({
            position: "absolute",
            top: top,
            left: left
        });
        left += 2*larguraAntes + palavra.largura;
    }
}

Well homogenous, no ? We now have room to maneuver to randomize each word. There is a space of larguraConteiner * horizontal before and after each word. Same for larguraAntes . I'm going to use half of that space (here you evaluate what's interesting, aesthetically speaking, in my opinion using the whole space left the appearance a bit bizarre).

        top: top + Math.floor(Math.random()*alturaAntes - alturaAntes/2),
        left: left + Math.floor(Math.random()*larguraAntes - larguraAntes/2)

End result . Each of these steps can be improved, if you wish, I did not spend much time with each of them not. Also, some limit conditions I believe may be bugged (for example, when testing using the whole space, some words have left out of the container) - but in the above example I believe this does not occur.     

Based on your fiddle, I decided to try to get the words to move from their original points, randomly at any angle, to a fixed distance of 25px, and the result until it was fine:

jsfiddle

Code:

CSS:

li {
    position: relative;
}

JavaScript:

var randomCoordsInACircle = function(cx, cy, radius) {
  var r2 = radius*Math.sqrt(Math.random());
  var angle = 2*Math.PI*Math.random();

  return {
    angle: angle,
    x: (r2 * Math.cos(angle) + cx),
    y: (r2 * Math.sin(angle) + cy)
  }
};

$(function () {
    $('li').each(function () {
        var rnd = randomCoordsInACircle(0,0,25);
        $(this).css({
            left: rnd.x.toFixed(0)+'px',
            top: rnd.y.toFixed(0)+'px'
        });
    });
})

Reference:

random point within a circle, even distribution, no problem, in javascript.

I think the simplest solution is to put all words in a paragraph instead of a list, and put the text-align attribute in justified. I used this solution precisely to show a tag cloud with most wanted topics on JavaScript .

<div style="text-align: justified; width: 20em">C C++ Java PHP JavaScript Lisp Scheme Haskell Lua Python Ruby Delphi Cobol</div>