MySQL’s InnoDB engine sports row-level locking, which can lead to deadlocks even when your code is inserting or updating a single row (specially if there are several indexes on the table being updated). Your best bet is to design the code around this in order to retry a transaction if it fails due to a deadlock. Some useful info about MySQL deadlock diagnose and possible workarounds is available here.
An interesting implementation of deadlock retry via AOP in Spring is available here. This way you just need to add the annotation to the method you want to retry in case of deadlock.