According to the Encyclopedia Virginia, Nathaniel Bacon was 73 when he died in 1692. This would mean he was born c.1619. The "Farmer's Register Vol. 7" contains the same age at death and indicates the information came from his tombstone at King's Creek, York County.
Nathaniel married twice. His first wife was the twice married widow, Ann Bassett Smith Jones. They married c.1655 and Ann died not long after. He married Elizabeth Tayloe (Taylor?) (nee Kingsmill) c.1656-57. The two books mentioned in the previous paragraph both say that there were no children born to either marriage. When Nathaniel died, his estate went to his niece Abigail Burwell and his horse was given to Lady Berkeley.
Elizabeth Holloway (nee Bacon) who married John Nuthall was first married to Dr. John Holloway. As John and Elizabeth married c. 1643-44 and Nathaniel and Elizabeth Tayloe did not marry until c. 1656, I don't think Nathaniel and Elizabeth Bacon could be considered as candidates for the parents of Elizabeth Nuthall.