Your definition of fiction and non-fiction (your point (3)) seems flawed. For one thing, a lot of what commonly goes under the non-fiction heading is false, at least in part. Think of an book about the bombing of Pearl Harbor which, although marketed as an accurate historical account, is full of errors. So, what's characteristic of a work of non-fiction is that it presents its content to be a true account of something in the real world.
Correspondingly, fiction might then be defined as a work that does not present its content to be a true account of something in the real world. Not presenting its content as true, such a work thus cannot be false (in relation to the real world) either. Someone who claims that Mark Twain's book is incorrect in some of what it says about Huckleberry Finn hasn't understood that this was meant to be a work of fiction. Works of fiction are neither true nor false much like -- to use a favorite example of Sidney Morgenbesser's -- the number 3 is neither married nor unmarried. Morgenbesser's point was that, while it is indeed not that case that the number 3 is married, calling it unmarried would inaccurately suggest that it is the kind of thing to which the married/unmarried distinction applies, that things of its kind could be married. Similarly, calling a work of fiction untrue or false inaccurately suggests that it is the kind of thing to which the true/false distinction applies and that it could be made true through suitable corrections of the text.
(I should say here in parentheses that works of fiction are often discussed in terms of truth and falsity. Thus, one Twain scholar may say to another: "You are quite wrong about Huck's feelings and motives on XYZ occasion..." Here the discussion is not about truth and falsity in relation to the real world, but in relation to the world of this work of fiction.)
Now let's think about your customer, and what s/he may have had in mind. I see three possibilities. First, and developing your point (4), one may think that the headings of "fiction" and "non-fiction" are not jointly exhaustive. Of course, this possibility is excluded if one of the headings is simply defined as covering everything not covered by the other. (My definitions work this way, as do yours.) But a plausible pitch can be made in favor of this possibility. Think of How-to books, for example, such as How to Live Well. This is not non-fiction by my definition (does not present its content to be a true account of something in the real world). But it's not really fiction either, in the sense in which this term is usually understood. So, employing a somewhat narrower definition of "fiction" than I have given, your customer may have thought that there is a third category of books covering (among other things, perhaps) advice about the aims and ambitions one should pursue in life.
Second, one may think that the two headings are not mutually exclusive. One could motivate this by saying that the fiction/non-fiction distinction is not binary (like odd/even, pregnant/non-pregnant), but scalar (like fast/slow). On this picture, books fall somewhere along a spectrum that ranges from a "fiction" pole at one end to a "non-fiction" pole at the other. You may object that the p/non-p terminology rules out this possibility. But ordinary language isn't so rigid. Think of the competitive/non-competitive distinction. I can easily imagine someone saying, in the context of a job search, that a candidate is not really competitive (in the sense of possibly being the most suitable candidate) and not really non-competitive (fit to be dropped from contention) either -- meaning that the candidate is somewhere in between and his application should be kept on hand for more detailed study later if more competitive candidates withdraw. In the fiction/non-fiction case, your example of a historical novel illustrates this possibility. Some of what's written in the book is, and some is not, presented as a true account of something in the real world. And the work is then a hybrid, somewhere between pure fiction and pure non-fiction. One could say about such a hybrid that it is both fiction and non-fiction (to some extent). But one could also (and perhaps in addition, thereby challenging what you write under your point (1)) say that it is really neither. This is analogous to how one might say that a hermaphrodite is neither purely female nor purely male, in a sense both, and in a sense neither.
The third possibility develops your point (4) in a different direction. It is another instance (one level up) of what I illustrated above with Sidney Morgenbesser's example. A predicate may be inapplicable to an object such that we should reject both the claim that the object is p and also the claim that it is not-p. The predicates even and odd are mutually exclusive and jointly exhaustive within a certain domain (natural numbers). But there are things outside this domain -- you and I, for instance -- and we are neither even nor odd (in the mathematical sense). So how does this apply to the fiction/non-fiction distinction? The number 3 would seem to fall outside the domain in which this distinction applies -- it makes no sense to ask whether this number does, or does not, present its content to be a true account of something in the real world. Of course, your customer was specifically searching for a book. So what books can we plausibly place outside the domain in which the fiction/non-fiction distinction applies? Well, notebooks containing only empty pages, presumably; and there are bound to be other examples.