It is not clear to me whether we can consider the Fisher's exact test as a "parametric" or "non-parametric" one. My gut feeling is that it should be defined as "parametric" as it involves a fully specified distribution (the hypergeometric). If so, however, I would not able to find an example of a non-parametric test for 2x2 contingency tables, which makes me wonder whether the distinction can be useful at all in this case.
tl;dr: Fisher's Exact Test is nonparametric in the sense that it does not assume that the population is based on theoretical probability distributions (normal/geometric/exponential etc.), but that the data itself reflects the parameters, which is why it proceeds with the assumption that the row/col totals are fixed.
Fisher's exact test, as its name suggests, gives the exact p-value rather than an estimation based on a particular sampling distribution thought to be aligning with the variable(s).
If you have two or more variables, all categorical/nominal, and your data consists of independent observations, then you can already intuitively create a cross-tabulation to assess conditional frequencies (akin to how you would want to see overlaps in a Venn diagram). For instance, say your independent variable is gender (M/F/O) and the dependent variable is party allegiance (D/R/I).
Now let's say we do not know the probability distribution of either variable, which means that we can't just plug the data into any parametric test. (In the classical FET where it's only a 2x2 (two dichotomous variables) which you know are binomially distributed, you could proceed using the hypergeometric distribution to estimate the p-value.)
Fisher's exact test directly gives us the probability of finding a result as extreme as the one we have. In other words, it reflects how far our observed frequencies are from the expected frequencies. If gender is truly independent of party membership, then there ought to be roughly uniform distribution. (Aside: you can use the 1 sample K-S test here to test for uniform distribution.)
But Fisher's test takes all the discrete values <= the observed ones, calculates their probabilities, and adds them up to give you the p-value, which you then compare to your alpha (probability of a Type I error, i.e. mistakenly rejecting the null hypothesis of there being no association between gender and party membership).
NB that although the FET is used as a recourse to the cross-tabbed chi square test when the sample size is low, the FET has its own assumptions -- I'd use it only for MECEly organised data such that the variables are 'really' nominal in a fundamental sense and not contrived for simplicity's sake (e.g. biological sex is 'truly' nominal if we use the usual definitions, whereas 'treatment status' must never be taken to be a true nominal variable) and where the individual instances are independently recorded.
For an actual rigorous idea of what the FET entails mathematically, take a look at Weisstein's neat definition -- http://mathworld.wolfram.com/FishersExactTest.html.
Fisher's exact test is a parametric test, because it does assume an underlying binomial distribution for the $2\times 2$ table. The table probabilities are then calculated conditioning on the total number of successes in an exact fashion. The term parametric refers to whether distributional assumptions are made about how the data arises, rather than, say, to whether a test statistic is calculated and then compared to some distribution (e.g. normal, t, $\chi^2$ etc.).
Consider the case of comparing two samples of dichotomous observations ("success" & "failure"), & taking one of the following approaches to defining a test statistic & its sampling distribution:
(1) Assume, under the null hypothesis, all observations are drawn independently from the same distribution & condition on the order statistic (sufficient for the distribution under the null). Decide that the count of "successes" in the first sample (or any equivalent) measures discrepancy with the null in the direction of the kind of alternatives you're interested in.
(2) Assume the observations in each sample constitute independent Bernoulli random variates. The population odds ratio is the parameter of interest & the overall odds of "success" is a nuisance parameter; the counts of "successes" in each sample are jointly sufficient & constitute binomial random variates. Condition on the total count of "successes", which is sufficient for the nuisance parameter & almost ancillary for the parameter of interest.
By now you're in the same place whether you've been shunning (1) or embracing (2) parametric assumptions while devising your test: with the count of "successes" in the first sample following a hypergeometric distribution under the null. (Putting to one side any subtle considerations that may arise from wanting to carry out a two-tailed test.) For observations that can take only two values the independently, identically distributed assumption alone entails a full parametrization of the distribution under the null after conditioning.
Tests that are used on nonparametric data can be used on any data normal or not normal (it is just in comparison to tests that can only be used on normal data they are less reliable). Fishers test is one of the tests that is actually prefered to use over chi-squared when the data is too small.