The suggestion that the converse might hold, that is, that every non-amenable group contains a free subgroup on two generators, was made by a number of different authors in the 1950s and 1960s.
Although von Neumann's name is popularly attached to the conjecture, its first written appearance seems to be due to Mahlon Marsh Day in 1957.
The historically first potential counterexample is Thompson group F. While its amenability is a wide-open problem, the general conjecture was shown to be false in 1980 by Alexander Ol'shanskii; he demonstrated that Tarski monster groups, constructed by him, which are easily seen not to have free subgroups of rank 2, are not amenable.
However, in 2003, Alexander Ol'shanskii and Mark Sapir exhibited a collection of finitely presented groups which do not satisfy the conjecture.
In 2013, Yash Lodha and Justin Tatch Moore isolated a finitely presented non-amenable subgroup of Monod's group.