Census data is only one tool in the arsenal that historians have for coming up with population estimates or other demographic information. From the standpoint of historiography, a census is no different than any other primary source record outside of the (sometimes questionable) assumption that it is more accurate due to government sponsorship. The key is figuring out where to look. Good places to start are tax records, military muster and conscription documents, feudal financial records, religious records (such as congregation sizes), etc.
When periodic census data is available, it is useful in forming the basis for fitting the other primary source material into extrapolation curves to provide more accurate estimates of the inter-censual periods.
Luckily someone else seems to have already done this leg-work - the data you are looking for likely exists, but might be difficult to track down if you are only looking online. The USDA sponsored a population survey by the Forest Service's Rocky Mountain Research Station about 10 years ago, and a paper was published on the methodology that they came up with.
You can find that paper (Coulson, David P. and Joyce, Linda. United States State-Level Population Estimates: Colonization to 1999) here. The appendixes give a really good description of the statistical methods they used and have some isolated samples of both the estimates they came up with as well as some of the primary source material that was used.
The resultant data set should be in the public domain (as it appears to have been prepared by U.S. government employees in the course of official duties), so you might be able to get your hands on it.
