InnoDb update deadlock

Question

I have a 10 millions rows innodb-table.

CREATE TABLE IF NOT EXISTS `books` (
  `id` int(10) NOT NULL AUTO_INCREMENT,
  `t` text NOT NULL,
  `book_id` int(8) NOT NULL,
  `key` varchar(7) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `key` (`key`),
  KEY `book_id` (`book_id`)
) 

At the beginning, columns book_id and key are zero/empty, and then it filling with query:

update books set book_id='123213', `key`='SOME_VARCHAR' where book_id='0' limit 1

And sometimes I have hard traffic on site and deathlocks on this query. Is there any solution for this or advice? Or maybe I need two tables for this.

p.s. Percona MySQL 5.5 with buffer pool size 3G, log size 512M. Dedicated server with Ubuntu with 8Gb RAM.