If you solve it by adding a secondary index then imho MyISAM or InnoDB won't matter much, as both use B-Tree indexes.
Append both additional columns to the index:
(col3, col1, col2) or
(col3, col2, col1) should behave the same for your query.
The reason to add all the columns is that such index covers your query - all data needed to resolve the query are contained inside the index, so it is not needed to read the actual rows from the table. That means the data you want to fetch are grouped together on disk (the index is ordered/clustered by
col3) and no random reads to the "main" table are needed.
If you had index on only
(col3) then each row may be stored in a different part of the table (depending on your primary key or order of inserts) and it would randomly jump all over the place, incurring IO penalty.
If you have no primary key, then MyISAM would be probably better, as InnoDB would create internal primary key and the table would take more space than needed.
But there is a possibility to solve it without using any secondary key. Use InnoDB table like
create table t (
col3 varchar(32) not null,
col4 smallint unsigned not null auto_increment,
primary key(col3, col4),
) engine = innodb;
That way the table will use InnoDB feature of clustering by primary key - effectively forcing the optimal order and grouping of rows described previously. And it will take just a small bit more space for the additional column (2 bytes only, if you are positive there will always be less than 60k rows) and much smaller secondary key to accomodate the
auto_increment behavior instead of effectively having 2 copies of the table as with the other version.