infochimps.org (http://infochimps.org/search?query=weight) is an easy search in general--it certainly has many health-related datasets, but I didn't see any specifically on exercise. The census bureau (http://www.census.gov/hhes/www/hlthins/hlthins.html) also collects some health data, though a good part of its focus is on insurance.
Most datasets on the web are going to be latitudinal surveys of a population in time, though they may span several years. It sounds like you might want a specific kind of longitudinal study following individuals over time and tracking their individual weight changes and relating that to their personal exercise routines. As garish as it is, http://www.bettycjung.net/Phdata.htm actually has a wide variety of health data links and is probably your best bet.
Finally, a few more links from my bookmarks which look like they might help you (though I haven't looked through them to be sure): http://www.who.int/whosis/en/, http://www.lib.berkeley.edu/PUBL/stats.html, and http://phpartners.org/health_stats.html. Good luck!