Silly me, I just solved it by re-reading what I thought I knew: array_rand (of course) returns the KEY of the array. Therefore, it works like:
// Query
$STH = $DB->prepare('SELECT * FROM players WHERE game = ?');
$STH->execute(array($_POST['game']));
// Get the stored photos
$Used = array();
while ($row = $STH->fetch())
$Used[] = intval($row['photo']);
// Get a random photo that is not stored already
$Array = array_diff(range(1, 6), $Used);
$PhotoKey = array_rand($Array);
$Photo = $Array[$PhotoKey];
// Insert the photo
$STH = $DB->prepare('INSERT INTO players (id, user, game, name, family, photo) VALUES (?, ?, ?, ?, ?, ?)');
$STH->execute(array($Id, $User->id, intval($_POST['game']), $Name, $Family, $Photo));