I make extensive use of "Google Advanced Search". I just entered Nicholas Lewis on the second line and New Kent Virginnia Foster on the first so that the search would narrow down. I immediately got a useful looking family tree at
http://archiver.rootsweb.ancestry.com/th/read/LEWIS/2000-03/0954523252
I say useful because it doesn't give primary sources, but the information on dates and places is relatively complete, so it feels somewhat reliable. That takes your Lewises back a couple of generations.
The next Google result was
http://boards.ancestry.com/localities.northam.usa.states.virginia.counties.newkent/42/mb.ashx.
This one doesn't give you answers, but it gives you some useful questions and lists some actual sources that may be worth consulting.
The next Google result is the same question but on Genforum -- easier to read, and I'm sorry ancestry.com closed it.
The Google result is your query -- wikitree gets stuff out there fast!
The next one after that is
http://archive.org/stream/parishregisterof00stpe/parishregisterof00stpe_djvu.txt
which is the actual Parish Register for New Kent County. This is unedited after it was scanned, so it's hard to read, but for documentation, it's pure gold, because it's a primary source, the original parish register. This won't give you all you want to know, but anything you find here, you can count on!
When I exhaust one Google search, I put some different words in based on what I already know, and Google usually gives me a few more interesting sources!