We propose estimators for the parameters of a linear median regression without any assumption on the shape of the error distribution including no condition on the existence of moments allowing for heterogeneity (or heteroskedasticity) of unknown form, noncontinuous distributions, and very general serial dependence (linear or nonlinear) including GARCH-type and stochastic volatility of unknown order. The estimators follow from a reverse inference approach, based on the class of distribution-free sign tests proposed in Coudin and Dufour (2009, Econometrics J.) under a mediangale assumption. As a result, the estimators inherit strong robustness properties from their generating tests. Since the proposed estimators are based on maximizing a test statistic (or a p-value function) over different null hypotheses, they can be interpreted as Hodges-Lehmann-type (HL) estimators. It is easy to adapt the sign-based estimators to account for linear serial dependence. Both finite-sample and large-sample properties are established under weak regularity conditions. The proposed estimators are median unbiased (under symmetry and estimator unicity) and satisfy natural equivariance properties. Consistency and asymptotic normality are established without any condition on error moment existence, allowing for heterogeneity (or heteroskedasticity) of unknown form, noncontinuous distributions, and very general serial dependence (linear or nonlinear). These conditions are considerably weaker than those used to show corresponding results for LAD estimators. In a Monte Carlo study on bias and mean square error, we find that sign-based estimators perform better than LAD-type estimators, especially in heteroskedastic settings. The proposed procedures are applied to a trend model of the Standard and Poor's composite price index, where disturbances are affected by both heavy tails (non-normality) and heteroskedasticity.