MySQL InnoDB Deadlock For 2 simple insert queries
HERE ARE THE FACTS

Here are the two INSERTs

insert into PlayerClub (modifiedBy, timeCreated, currentClubId, endingLevelPosition, nextClubId, account_id) values (0, '2014-12-23 15:47:11.596', 180, 4, 181, 561)
insert into PlayerClub (modifiedBy, timeCreated, currentClubId, endingLevelPosition, nextClubId, account_id) values (0, '2014-12-23 15:47:11.611', 180, 4, 181, 563)


Here are the two lines from your SHOW ENGINE INNODB STATUS\G

RECORD LOCKS space id 49735 page no 4 n bits 72 index `UK_cagoa3q409gsukj51ltiokjoh` of   table `db`.`playerclub` trx id 19896526 lock_mode X insert intention waiting
RECORD LOCKS space id 49735 page no 4 n bits 72 index `UK_cagoa3q409gsukj51ltiokjoh` of   table `db`.`playerclub` trx id 19896542 lock_mode X


OBSERVATIONS

You doing an INSERT with two different account_ids: 561 and 563.

They are unique and should not have issues, right ? WRONG !!!

Due to InnoDB's Clustered Index, there can still be a deadlock. Why ?

Look back at your two INSERTs. The PRIMARY KEY on id in not specified. It must be auto generated. Any key other than the PRIMARY KEY (unique or non-unique) will have the PRIMARY KEY attached.

Please note the MySQL Documentation on how a Secondary Index and a a Primary Key are intertwined:


  All indexes other than the clustered index are known as secondary indexes. In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index.
  
  If the primary key is long, the secondary indexes use more space, so it is advantageous to have a short primary key.


Although you are inserting account_id 561 and 563, under the hood you are insert 561-(id) and 563-(id) into the UK_cagoa3q409gsukj51ltiokjoh index. The PRIMARY KEY becomes the bottleneck because the Secondary Index has to wait until the id column is auto_generated. 

RECOMMENDATION

You have a table with two candidate keys


PRIMARY KEY on id
UNIQUE KEY on UK_cagoa3q409gsukj51ltiokjoh


Since both are BIGINT, you could increase performance and have a smaller PlayerClub table by getting rid of id and still maintain uniqueness because of UK_cagoa3q409gsukj51ltiokjoh as well as avoiding this deadlock situation.