OK I have solved the issue. sama55 is completely correct. I wrote some PHP code to set the foreign key check to 0 in qa-db-install.php
Here is the code from lines 1364-1381 (changed parts are highlighted):
case 54:
qa_db_query_sub("SET FOREIGN_KEY_CHECKS=0;");
qa_db_upgrade_query('UNLOCK TABLES');
qa_db_upgrade_query(qa_db_create_table_sql('userlevels', array(
'userid' => $definitions['userlevels']['userid'],
'entitytype' => $definitions['userlevels']['entitytype'],
'entityid' => $definitions['userlevels']['entityid'],
'level' => $definitions['userlevels']['level'],
'UNIQUE userid (userid, entitytype, entityid)',
'KEY entitytype (entitytype, entityid)',
QA_FINAL_EXTERNAL_USERS ? null : 'CONSTRAINT ^userlevels_ibfk_1 FOREIGN KEY (userid) REFERENCES ^users(userid) ON DELETE CASCADE',
)));
$locktablesquery.=', ^userlevels WRITE';
qa_db_upgrade_query($locktablesquery);
qa_db_query_sub("SET FOREIGN_KEY_CHECKS=1;");
break;