The falsifiability of natural selection
What is natural selection?

Natural Selection (NS) is an evolutionary process causing a directional change in both a phenotypic trait and the allele frequencies associated with particular values of this phenotypic trait whenever there is a trait that 


Has a non-zero narrow-sense heritability $h_N^2$


See this post for the definition of heritability
Note that if $h_N^2 ≠ 0$, then it necessarily implies that the trait is variable in the population.

Correlate with fitness variance in the population


See this wikipedia article for the definition of correlation



You may want to have a look at this post (maybe in particular Lewontin's recipe explained in this answer) or have a look at an intro course to evolution such as Understanding Evolution by UC Berkeley if this is unclear to you.

You may also want to have a look at the post How is “selection” best defined?

Note about the environment

Note that the genotype - fitness covariance does not necessarily need to be dependent or correlated with a specific environmental variable. Many selection pressures are indeed independent of the environment. If one specific genotype is associated to heart failure, then the environment may matter little. This genotype will always be associated with lower fitness. 

In other words, you do not need environmental change, or environment specific adaptations in mind to test NS.

Would evidence that what is needed for natural selection to happen does not exist falsify NS?

Mutations

I don't think that an evidence that mutations do not occur would falsify NS because while NS needs genetic variation (fuelled by mutations), the process per say does not refer to the creation of new genetic variance via mutations. Showing that mutation do not occur would not per say falsify NS (I think) but it would make the point that NS cannot happen. A bit like, the absence of energy would not falsify the theory of gravity but it would prevents any gravity to ever happen.

The theory of evolution as whole would be falsified if one were to show mutations never occur (or occur at a much lower or much higher rate than currently observed) though.

Heritability

Similarly, if one could show that $h_N^2 = 0$ for all traits (nothing is heritable), then this would also prevent any NS to ever happen

Fitness variance

Similarly, if one could show that there is no fitness variance in population or even that fitness is always independent of the gentic variance (in other words, fitness itself is not heritable), then NS would never happen.

How to falsify natural selection?

You could show that for a phenotypic trait $h_N^2 &gt; 0$ and show that genetic variance correlates with fitness variance (fitness can be measured as the number of offsprings) and yet repeatedly fail to see any change in the phenotypic trait values (or frequency of the loci explaining variance for this trait) over time. Such observations would falsify NS.