Can a novel protein domain arise de novo in nature or did all protein domains evolve from a single ancestor?
Yes. Novel protein domains can arise de novo in nature. The evidence is quite solid as those new domains show all the expected mutation patterns and statistical properties (expected for something evolving from DNA that doesn't yet encode for a domain). E.g.: see the following meta-analysis, which also describes how those new domains behave relative to older ones, and how they integrate into proteins: Toll-Riera et Mar Alba 2013, BMC Evolutionary Biology, "Emergence of novel domains in proteins":  https://bmcevolbiol.biomedcentral.com/articles/10.1186/1471-2148-13-47  

If you are additionally interested in new genes, the following mini-review: http://www.sciencedirect.com/science/article/pii/S0960982214001547#bib20 .

If you are additionally interested in in-vitro evolution, which is directly observable within the life-span of single humans, the following review: http://www.sciencedirect.com/science/article/pii/S0022175904001309