Why does this result seem "wrong?" A Bayesian would say that the result seems counter-intuitive because we have "prior" beliefs about when the sun will explode, and the evidence provided by this machine isn't enough to wash out those beliefs (mostly because of it's uncertainty due to the coin flipping). But a frequentist is able to make such an assessment, he simply must do so in the context of data, as opposed to belief.
The real source of the paradox is the fact that the frequentist statistical test performed doesn't take into account all of the data available. There's no problem with the analysis in the comic, but the result seems strange because we know that the sun most likely won't explode for a long time. But HOW do we know this? Because we've made measurements, observations, and simulations that can constrain when the sun will explode. So, our full knowledge should take those measurements and data points into account.
In a Bayesian analysis, this is done by using those measurements to construct a prior (although, the procedure to turn measurements into a prior isn't well-defined: at some point there must be an initial prior, or else it's "turtles all the way down"). So, when the Bayesian uses his prior, he's really taking into account a lot of additional information that the frequentist's p-value analysis isn't privy to.
So, to remain on equal footing, a full frequentist analysis of the problem should include the same additional data about the sun exploding that is used to construct the bayesian prior. But, instead of using priors, a frequentist would simply expand the likelihood that he's using to incorporate those other measurements, and his p-value would be calculated using that full likelihood.
$L = L$(Machine Said Yes | Sun Has Exploded) * $L$(All other data about the sun | Sun Has Exploded)
A full frequentist analysis would most likely show that the second part of the likelihood will be much more constraining and will be the dominant contribution to the p-value calculation (because we have a wealth of information about the sun, and the errors on this information are small (hopefully)).
Practically, one need not go out and collect all data points obtained from the last 500 years to do a frequentist calculation, one can approximate them as some simple likelihood term that encodes the uncertainty as to whether the sun has exploded or not. This will then become similar to the Bayesian's prior, but it is slightly different philosophically because it's a likelihood, meaning that it encodes some previous measurement (as opposed to a prior, which encodes some a priori belief). This new term will become a part of the likelihood and will be used to build confidence intervals (or p-values or whatever), as opposed to the bayesian prior, which is integrated over to form credible intervals or posteriors.