Avalanche effect sample size
You can use the Frequency test of the NIST statistical random number test suite. ( see http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf, chapter 2.2).
In that chapter is also stated the recommended sample size.

I would propose to encrypt a block of zeroes with different randomly selected keys.

Another test would be to fix the key and use random plaintexts $t$, encrypt it $c= enc(t)$ and fit $t \oplus c$ to the frequency test.