Invalid deadlock error when updating multiple rows to NULL without a PK

This bug was previously filed as

https://github.com/codership/galera/issues/137

but Alex thinks that it belongs to Launchpad:

create table t1(value integer) engine=innodb;
insert into t1 values (1), (2);
update t1 set value=NULL;
update t1 set value=NULL;
ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction
drop table t1;

This issue is not reproducible if a primary key is present or if the values being updated to are non-NULL.