As you noted, there are no birth certificates in North Carolina until the 20th century. Some suggestions - Fuller was married in Alabama, so you could look for a marriage bond - sometimes a parent or sibling is also on the bond. "Fuller" and "Bryant" are surnames, so you might search for them in North Carolina, perhaps in probate records (on the theory that one or both were the names of a grandparent) or try looking for Fuller, Bryant, and Walker near one another on a census. People often emigrated in family groups, so looking for other Walkers living near Fuller in Alabama might turn up a relative. He ought to be on the 1840 census in either Alabama or North Carolina, but if he was still living with his parents he wouldn't show up by name.
