Ruby, 39 characters
The idea to use a cross-join shamelessly stolen from Johannes Kuhn's Java answer.
We can shave off four characters (getting to 35) if we tune the code to a specific environment. JRuby's console IRB is single-threaded:
This is my previous solution:
getting a thread stuck on a mutex is easy:
but this isn't a proper deadlock, because the second thread is technically not waiting for the first thread. "hold and wait" is a neccessary condition for a deadlock according to Wikipedia. The first thread doesn't wait, and the second thread doesn't hold anything.
97 95 characters
this is a classic deadlock. Two threads compete for two resources, retrying if they succeed. Normally they get stuck within a second on my machine.
But, if having infinitely many threads (none of which consumes CPU infinitely and some of which deadlock) is OK,
87 85 characters
According to my test, it fails after the thread count reaches about 4700. Hopefully it doesn't fail until each thread had a chance to run (thus either deadlocking or finishing and freeing space for a new one). According to my test, the thread count doesn't drop after the failure occurs, meaning that a deadlock did occur during the test. Also, IRB died after the test.