jdbc+mysql: "Deadlock found when trying to get lock; try restarting transaction"
Looking at the Stored Procedure, I see something rather unnatural.
DELIMITER $$

DROP PROCEDURE IF EXISTS `adam_matan`.`AddPixel` $$
CREATE PROCEDURE `adam_matan`.`AddPixel`
(
    GivenType VARCHAR(20),
    GivenPixelData BLOB
)
TheStoredProcedure:BEGIN

  DECLARE KeepPixels,DeleteLimit,MaxID INT;

  SET KeepPixels = 5;
  SET DeleteLimit = 100;

  INSERT INTO pixels (type,pixel_data)
  VALUES (GivenType,GivenPixelData);
  SELECT MAX(ID) INTO MaxID FROM pixels;
  IF MOD(MaxID,DeleteLimit) &gt; 0 THEN
      LEAVE TheStoredProcedure;
  END IF;

  DROP TABLE IF EXISTS pixel_window;
  CREATE TEMPORARY TABLE pixel_window
  (id INT NOT NULL PRIMARY KEY) ENGINE=MyISAM;

  SET @sqlstmt= CONCAT('INSERT INTO pixel_window ',
      'SELECT id FROM pixels WHERE type=''',GivenType,
      ''' ORDER BY id DESC LIMIT ',KeepPixels);
  PREPARE st FROM @sqlstmt; EXECUTE st; DEALLOCATE PREPARE st;

  SELECT * FROM pixels WHERE type=GivenType ORDER BY id; SELECT SLEEP(10);
  DELETE A.* FROM pixels A LEFT JOIN pixel_window B USING (id)
  WHERE A.type=GivenType AND B.id IS NULL;
  SELECT * FROM pixels WHERE type=GivenType ORDER BY id;
  DROP TABLE IF EXISTS pixel_window;

END $$

DELIMITER ;

The thing I see that is unnatural is the DELETE ... JOIN query that is mixing an InnoDB table and a MyISAM table. Such JOINs tend to be rather clumsy to mysqld.
Let's make the pixel_window table. InnoDB. In fact, let's not make it a temporary table. Of course, the hard part is to create a unique pixel_window table for the session. The pixel_window temp table will be the prefix 'pixel_window_' with the Connection ID appended.
DELIMITER $$

DROP PROCEDURE IF EXISTS `adam_matan`.`AddPixel` $$
CREATE PROCEDURE `adam_matan`.`AddPixel`
(
    GivenType VARCHAR(20),
    GivenPixelData BLOB
)
TheStoredProcedure:BEGIN

  DECLARE KeepPixels,DeleteLimit,MaxID INT;

  SET KeepPixels = 5;
  SET DeleteLimit = 100;

  INSERT INTO pixels (type,pixel_data)
  VALUES (GivenType,GivenPixelData);
  SELECT MAX(ID) INTO MaxID FROM pixels;
  IF MOD(MaxID,DeleteLimit) &gt; 0 THEN
      LEAVE TheStoredProcedure;
  END IF;

  SET @pwtable = CONCAT('pixel_window_',CONNECTION_ID());

  #
  # Create the pixel_window Table
  #
  SET @sqlstmt = CONCAT('CREATE TABLE ',pwtable,' (id INT NOT NULL PRIMARY KEY) ENGINE=InnoDB');
  PREPARE st FROM @sqlstmt; EXECUTE st; DEALLOCATE PREPARE st;

  #
  # Load the pixel_window Table
  #
  SET @sqlstmt= CONCAT('INSERT INTO ',@pwtable,' ',
      'SELECT id FROM pixels WHERE type=''',GivenType,
      ''' ORDER BY id DESC LIMIT ',KeepPixels);
  PREPARE st FROM @sqlstmt; EXECUTE st; DEALLOCATE PREPARE st;

  SELECT * FROM pixels WHERE type=GivenType ORDER BY id; SELECT SLEEP(10);

  #
  # Use the pixel_window Table to perform DELETE...JOIN
  #
  SET @sqlstmt = CONCAT('DELETE A.* FROM pixels A LEFT JOIN ',
  @pwtable,' B USING (id) WHERE A.type=GivenType AND B.id IS NULL');
  PREPARE st FROM @sqlstmt; EXECUTE st; DEALLOCATE PREPARE st;

  SELECT * FROM pixels WHERE type=GivenType ORDER BY id;

  #
  # Drop the pixel_window Table
  #
  SET @sqlstmt = CONCAT('DROP TABLE IF EXISTS ',@pwtable);
  PREPARE st FROM @sqlstmt; EXECUTE st; DEALLOCATE PREPARE st;

END $$

DELIMITER ;

Give it a Try !!!
CAVEAT : Since I created this monster, I needed to slay it as well.