How do frequentists address this paradox of hypothesis testing? Suppose we sample a person from the population. They are a member of US Congress. We define the null hypothesis $H_0$ as "the person is American". We calculate the $p$-value: $P[member\ of\ Congress | American] \ll 0.05$. Since if the null hypothesis holds, the person is very unlikely to be a member of Congress, we reject the null hypothesis and decide that the person is very likely not an American. This conclusion is obviously very wrong, as all members of Congress are American.
Which assumptions of the hypothesis testing did I violate here? In other words, if I encounter a similar (but more obscure) application where this methodology is also not appropriate, how do I identify it?
Edit: to clarify the methodology. In Fisher's example, where he is trying to identify if the tea-drinking lady can correctly identify cups of tea, he considers the chances of her guessing all cups of tea correctly if she had no ability:

Given that if she had no ability, it would be very unlikely for her to guess all cups of tea correctly, he rejects the hypothesis of her having no ability. So the conclusion is that it is unlikely that she has no ability and just got lucky. Which makes perfect sense.

In my example, given that if the person was an American, it would be very unlikely for them to be a member of Congress, we reject the hypothesis of them being an American. So we conclude that it is unlikely that they are an American and we just got lucky picking a Congressman out of all Americans.
So is the reason for this paradox the formulation of the alternative hypothesis? To reach the paradox, we have to assume that the alternative hypothesis forms a disjoint set with the null hypothesis. E.g. alternative of "no ability" is "has ability"; alternative of "population of Americans" is "population of non-Americans". Whereas all we can say is that the alternative hypothesis is some different population than the null hypothesis - it could be a subset! E.g. alternative to "No ability" could be "Someone told her the correct ordering", and alternative to "population of Americans" could be "population of Americans in Washington, DC"? So rejecting the null hypothesis is correct in both cases - it is indeed unlikely that we sampled from all Americans and stumbled on a US congressman - and the paradox arises from jumping to a particular alternative hypothesis and "accepting" it for no good reason? While in fact we cannot say anything about any alternative from the experiment - ALL we know is that the null was unlikely to cause the observation!
 A: Frequentist statistics is meant to make inference on populations using samples, not on individuals. You first define a population (which you have not done), take a sample, and make inference on the population using the sample, taking into account the uncertainty.
You have used your sampled individual as if it were your population, and try to make inference on him. But frequentist statistics do not apply here, you cannot repeat the sampling processs with a population size of 1. 
A: To make this test apply to the population we could change the hypotheses slightly to 
H0: The sample is drawn from a population in the US
H1: The sample is drawn from a population not in the US
As far as I can tell there's nothing wrong with this hypothesis test. For a hypothesis test with significance level 0.05 (for example) is a test you need that if the null hypothesis is true then the probability that the test will reject it is less than 0.05.
In this example if you think about repeatedly sampling, if the null hypothesis then we will choose people from the US. And out of those people, only a very small fraction (less than 0.05) are expected to be members of congress, so you would only reject the null hypothesis for less than 5% of them.
So if the test is correct, why does it seem so paradoxical? While it technically satisfies the criterion for a hypothesis test, for any fixed significance level we typically want to choose the rejection criterion which maximizes the power of the test - that is it maximizes the probability of rejecting the null hypothesis if it is false. In your case the test is terrible at this, it will never reject the null hypothesis when it is false. 
The paradox depends on the rejection criterion being impossible under the alternative hypothesis or more unlikely than under the alternate hypothesis that under the null. Any such test will have zero or very low power. 
A: I'd say there's at least two additional problems with your "paradox" (I don't even think it is a valid testing problem): 
First, "Member of Congress=1" I'd say a useless test statistic $T(X)$ for your "H0" as it does not measure deviation from the H0. So, a person who is not American would have automatically "Member of Congress=0" which also applies to most Americans. A test statistic should be something that collects evidence against the H0. If enough evidence is collected, we eventually reject H0. You need a point that is in in perfect accordance with the H0, say T(X)=0; then a T(X)≠0 should carry more information against H0 then T(X)=0. Let me expand on that. What values can the test statistic take? Well 1 if the person is a member of congress AND American and 0 if the person is either American AND not member of congress, OR Non-American. That means that the test statistic can take on TWO distinct values (0, 1) if the null were true! And both values do carry information in favour of the H0 (0 for Americans non-congress members, 1 for American congress members). But one of these values (0) also carries information in favour against the H0. So what does one learn about H0 in case the test statistic is 0 or not 0, especially with n=1? Thus the test you describe appears invalid to me (in the sense of the test keeping its $\alpha$ for every $\alpha \in [0;1]$). It is most certainly also inadmissible, i.e., there is a test for that H0 having better power. 
Second, the p-value is defined as the probability to observe a test statistic that speaks as much or more strongly against the H0 as the value you have observed in the sample. In other words, it is a quantile of the distribution of the test statistic under the assumption the null were true. I have difficulties to match your p-value, which seems to simply be a conditional probability, to that. But not every conditional probability conditioning on "American" is automatically the correct p-value because for that one would have to work out the correct null distribution of the test statistic that you propose. Here $T(X)$ is 1 iff congress & American. 0 if American & not congress or 0 if Non-American, for which I have difficulties translating what you call "H0" properly to a condition under which to derive the null distribution. Would you say the value of $T(X)$ corresponding to perfect agreement with H0 is $T(X)=1$ or $T(X)=0$, or both, for the population of "all people on earth"? Or do you restrict yourself to "all people in the US", "people who are US citizens" etc.? All that would be needed to derive the proper null distribution for the test statistic.        
A: When we do hypothesis testing, we need to decide how willing we are to be wrong. $\alpha$ is the proportion of times when $H_o$ is true that we reject it. When we reject the null hypothesis, we are not saying that the null hypothesis definitely is false, we're saying that we have performed a test that has at most $\alpha$ chance of being wrong. If you were to try the hypothesis testing you describe, you would have less than 5% change of incorrectly rejecting the null hypothesis.
Note that your formulation is ordered incorrectly, however. In a valid hypothesis test, you have to state what the rejection region is before collecting any statistics. You describe observing whether the person is a member of Congress before you describe this being part of the rejection region. I'm taking your order of description to be chronological order; if you were to decide after seeing that the person is a member of Congress that that should be a basis of rejection $H_o$, that would be post hoc hypothesis testing, which isn't valid.
It is not correct phrasing to saying that the null hypothesis is unlikely to true. In hypothesis testing, we are decisioning entirely on the probability of seeing the result given the null hypothesis, not the probability of the null hypothesis given the result. "we ... decide that the person is very likely not an American" would be fallacious even if you had a better test.
It absolutely true that in doing hypothesis testing, there is some sense in which it is not necessary to pick a statistic that makes sense. If you roll a D20 and reject the null hypothesis whenever it comes up 20, that is a hypothesis test with $\alpha=.05$. Your example shows that statistical tests should be evaluated based not only on $\alpha$, but on power (1-$\beta$). In my example, the power is 5%: if the null hypothesis is false, I have only 5% chance of rejecting it. Since the power and $\alpha$ are equal, this test doesn't actually have any diagnostic value. Whether a hypothesis test is valid, and whether it is at all worthwhile, are two different issues. You can't tell just from the p-value how much you should update your beliefs.
In you example, the probability of a non-American being a member of Congress is zero. So your power is less than your $\alpha$, which makes your test worse than useless.
A: I can't say for certain, but I'm guessing you're making a rather frequent mistake:
You're (implicitly) misinterpreting p-values.
A very, very common misinterpretation of p-values is "a p-value is the probability that the null hypothesis is correct." That's wrong. Instead, the p-value is the subtly different probability that, given that the null hypothesis is correct, what's the probability that you'll see results as or more extreme than you did?
This misintepretation is somewhat implicit in your logic. I'm guessing you're thinking along the lines of "Okay, the p-value says the null hypothesis is really, really unlikely. Wait - what gives? The setup of the experiment is such that it should be very, very obvious that the null hypothesis is near certain? Why is the p-value near zero when the probability of the null hypothesis being true is near one?" -- The answer to that is, again, that the p-value is not measuring the probability that the null hypothesis is true.
So what is the p-value? It's not the probability of the null hypothesis (the p-value conditioned on the null hypothesis being true, so certainly it can't be that). Instead it's the probability of the data. -- But remember we're in a frequentist framework. What does "the probability of the data" actually mean? For frequentists, the probability is the number of times an event happens over the total number of trials. The data we have is the data we have. Number of trials equals one, so how are we getting fractions here?
The trick is that the number of trials is not our actual experiment. Instead, it's a hypothetical set of experiments under the assumption the null hypothesis is true. We don't run the (theoretical) experiment once, we run it multiple times. If we do this (sample under the assumption that the people we sample are Americans), we see that the chance of getting "congressman-ness" at-or-more-extreme than our initial trial is very, very low. In fact, it's equal to the p-value.
Implicit in the concept of using p-values in null hypothesis testing is the concept that you're sometimes going to get it wrong. You will occasionally get experimental results where you'll inappropriately discard the null hypothesis. In fact, you'll inappropriately discard it (p-value) fraction of the time that the null hypothesis is actually true. (Assuming a large number of independent experiments.)
So, yeah, in your example the null hypothesis is true and you were unlucky and happened to get results which inappropriately discarded it. But the p-value tells you there's a small probaility that would happen. If you repeated the experiment (given that the null hypothesis is true), what's the chance you'll get a congressman the next time? Pretty darn low, just like the p-value says.
Also, 0.05 is not a magic number. It's rather arbitrary. There isn't much a priori rationale in choosing 0.05. R.A. Fisher used it, so it has a certain cachet, but it's not the most appropriate value in all situations.  One in 20 just seemed like a reasonable compromise at the time between falsely rejecting the null hypothesis versus making things too stringent and never rejecting the null hypothesis, even when you should. 
In particular, if you're concerned about making Type I errors (that is, rejecting the null hypothesis when it's actually true), you will need to tighten your p-value cutoff. The most common example of this is with multiple-testing situations, where you're performing a number of null hypothesis tests of different sorts. You will get a certain error rate, so people reduce the p-value threshold to avoid spurious rejections. But you also can (and should) change your p-value cutoff if the damage of incorrectly rejecting the null hypothesis is significantly greater than missing situations where the null hypothesis is incorrect.
A: Your definition of p-value is not right here. Note that p-value is the probability under null to get at least as extreme observation as the observed one. You defined it as the probability of getting the observation under null. Let's formalize the problem. Essentially you are drawing a sample of size 1 from an unknown population, and you want to test whether the population proportion, $\pi$, of Americans in your population is equal to $1$. Your alternative hypothesis is that $\pi=0$.
In your sample, you have $X$ = Number of congressmen in the sample, which can be either 0 or 1. To define p-value, you have to ask "Which value of $X$ is a larger evidence against the null?" Clearly it is 0. Therefore your p-value should be defined as $P_{H_0}(X \leq X_{obs})$, which is not small when $X=1$. In fact, it is equal to 1. Even if you get $X=0$ in your sample, your p-value will still not be small and you will end up accepting the null either way. That is because you have a very low-powered test due to having sample size = $1$.    
Again, focus on the part 'at least as extreme as the observed one'. In the lady tasting tea problem, the lady getting correct answer is more evidence against the null, therefore the higher the number of correct answers the more extreme it is. Since she got all of them correct in the sample, the observed data was the most extreme situation. Therefore the p-value was defined as the probability of that case only. If she answered only one wrong, p-value would have been probability of getting one wrong + probability of getting correct.  
A: Your null hypothesis seems to be "This person is American"
So presumably your alternative hypothesis is "This person is not American"


*

*"This person is a member of the US Congress" is then not an extreme result in terms of being American or not.  Indeed it points towards the null hypothesis 

*"This person is a king or queen or prince or princess" might be an extreme result in terms of the hypotheses, even taking Megan Markle and Lisa Halaby (and a few others) into account  
