For one-way anova type models you could do a permutation test. Just use the median polish to fit the model, then choose an overall summary variable (you could do the traditional anova F-ratio, or the biggest difference between group coefficients, or something else that is a measure of the spread between the groups).
Now randomly permute which observations are in which groups and recompute the statistic, repeat this a bunch of times. The p-value is the proportion of times the computed statistics is equal to or more extreeme that that for the original data.
For a 2-way or factorial you can still do the permutations, but how you permute will depend on the hypothesis to be tested.