I don't have time to answer this properly, but I'll get you headed in the right direction. Perhaps some bounty hunter will fill in the details [or you can]. I would start by including edges independently with probability $p = cn^{-2/r}$ (this will roughly give your average degree condition). For a given $r$ vertices and another given $r$ vertices, there are $r^2$ edges to check to see if there is a $K_{r,r}$ (note that I specify the partition beforehand). The probability that there is a $K_{r,r}$ on this specific partition is $(cn^{-2/r})^{r^2} = c^{r^2} n^{-2r}$. Since there are at most $n^{2r}$ partitions to check, the probability that you have at least one $K_{r,r}$ is (by a union bound) at most $n^{2r} \cdot c^{r^2} n^{-2r} = c^{r^2}$. So $1-c^{r^2}$ proportion of the graphs have no $K_{r,r}$ . Now you just need to argue that the one of the graphs in this proportion meets your average degree condition.
Note that the expected value of the number of edges is $c\binom{n}{2}n^{-2/r}$, by linearity of expectation. Most of this binomial random variable is concentrated close to expected value [using concentration results; Chebyshev might be enough here, or some other result might work]. This should be able to finish it off, as it will give that for suitable $c$ most of the graphs have high average degree, and also most of the graphs have no $K_{r,r}$. If most have one property or the other, then there has to be one with both of those properties.
Good luck, and I hope this argument works out (again, I haven't filled in the details, will someone come along and write this up properly?)