What happens if two mySQL queries both try to lock the same row at the same time? So this isn't exactly my strong suit, but here's my basic understanding of the situation:

If two threads of the same application both try to execute the same query at the same time, mySQL will experience deadlock.  The way to prevent deadlock is by locking the table (or row) before writing to it.  But what if the locking requests happen simultaneously?

e.g. you have a table like:

#my_table
---------------
| key | value |
---------------
|  1  |  foo  |
---------------
|  2  |  bar  |
---------------


Then I write a query in my application that does something like 

LOCK TABLES my_table WRITE;
UPDATE my_table SET value = RAND() WHERE key = 2;
UNLOCK TABLES;


and by some miracle two instances of this query fire in the exact same millisecond (nanosecond?) what would happen?  It's an InnoDB table if that matters.
This is not a deadlock.

One transaction will simply block -- waiting to acquire the lock. The other transaction will proceed. As soon as the other transaction is done -- either by commit or rollback, the first transaction will proceed.

A deadlock happens when a transaction has acquired a lock on object A, and attempts to acquire a lock on object B at the same time as another transaction has already acquired a lock on object B and is attempting to acquire a lock on object A. Both transactions will then block, waiting on each other. That's the definition of a deadlock: two transactions blocked waiting on a lock that the other has.