InnoDB query duration inconsistent
ASPECT #1 : InnoDB

What immediately catches my eye is the fact that the table has no explicit PRIMARY KEY. This means that an internal rowID Clustered Index (gen_clust_index) is being used.

With each UPDATE command, you may encounter moments when the row is actually locked in conjunction with the Clustered Index. Consequently, the data page gets locked.

Here is a question: Is it possible for the PRIMARY KEY (or rowID) of two different rows to deadlock? Surprisingly, the answer is Yes. Rather than explain why, I will refer you to three questions asked by one person: RedBlueThing.

I managed to answer his three questions about deadlocking pages:


Jun 14, 2011 : Reasons for occasionally slow queries?
Jun 08, 2011 : Will these two queries result in a deadlock if executed in sequence?
Jun 06, 2011 : Trouble deciphering a deadlock in an innodb status log


It is possible that two or more rows occupy the same data page. In fact, the rowID-based PRIMARY KEY coexists with the data on the same data page. While crisscrossing rows, perhaps some miscellaneous garbage collection (data structures within the InnoDB Buffer Pool that are released and reallocated) may be happening. 

ASPECT #2 : Your C# Code

Inside the loop, you are also doing garbage collection and reallocation for the DB Connector. That needs to be reorganized, perhaps placing it outside the loop.

SUGGESTION

Try setting up the test using the transaction paradigm with BeginExecuteNonQuery()

MySqlCommand cmd = new MySqlCommand();
cmd.Connection = conn;
cmd.BeginExecuteNonQuery();
for (int i = 0; i &lt; 15; i++) {
   long start = CurrentTimeMillis();

   cmd.CommandText = "UPDATE test SET col1=" + i + " WHERE col2=1";
   cmd.Prepare();
   cmd.ExecuteNonQuery();

   Console.WriteLine("Duration: " + (CurrentTimeMillis() - start));
}
cmd.EndExecuteNonQuery();


Give it a Try !!!