By my calculations, you'd only need to spin up 50 or so amazon instances, and they could cover the entire IP space in a day doing 1k pings/second each.
These guys have been mapping the IPv4 space via ping over time (since 2003) and have an interactive browsable map that also shows blocks marked for localhost/private networks/multicast, etc and which registrars control which regions. It is pretty neat. Most recent data is Nov 2010. Since then the 11 /8 blocks that show as free have been allocated.
http://www.isi.edu/ant/address/