Option 1: Change engines
First thing to do, if at all possible, is probably change
InnoDB, which handles concurrency much better. See "MyISAM vs InnoDB", specially the point about "Table-locking vs Row-locking". I quote them:
When a query runs against a
MyISAM table, the entire table in which it is querying will be locked. This means subsequent queries will only be executed after the current one is finished. If you are reading a large table, and/or there are frequent read and write operations, this can mean a huge backlog of queries.
When a query runs against an
InnoDB table, only the row(s) which are involved are locked, the rest of the table remains available for CRUD operations. This means queries can run simultaneously on the same table, provided they do not use the same row.
Option 2: Master/Slave replication
Another possible (although probably not cheap) solution is to have your database being replicated using an asynchronous Master/Slave setup. [I guess that if you cannot change from MyISAM to InnoDB, it won't be easy to setup a replicated DB... but I don't know either your possibilities nor your limitations.]
Your users (i.e.: your application) should always be working with your Master node, and all
DELETEs should always and only be executed there. The
SELECTs can be executed in either node, taking into account that the Slave might be slightly not up-to-date. The
SELECTs that take a long time should be executed in the Slave, so all the users in the Master node are not blocked at all.
The Slave node can not be completely up-to-date (as the replication is asynchronous, it can lag behing the master by anything from a few miliseconds to a long time, if the Slave could not process the updates from the master and they "accumulate").
This kind of scenario is not uncommon in applications where you have the Master node working with a setup optimized for OLTP (OnLine Transaction Processing); and the Slave node with a setup optimized for OLAP (OnLine Analytical Processing). OLTP means (mostly) entering and manipulating data, and making relatively simple queries, with small amounts of data every time, whereas OLAP means querying data, normally in large amounts and with aggregations and computations (i.e.: analysis and reporting).