In exploratory analysis you have much more latitude for how you generate the hypotheses of interest, since there is no biasing of tests due to optimisation processes. (Of course, for this to apply you should ensure that when you undertake confirmatory analysis on the hypotheses, you use different data.) Nevertheless, that does not mean that there is no difference in optimality of different kinds of processes that can be used to identify hypotheses of possible interest. So while you can, in theory, "do whatever you want", you probably shouldn't.
Generally speaking, in exploratory analysis you will still want to identify hypotheses that have some evidentiary basis, so that you don't waste time testing lots of false hypotheses in the confirmatory phase. For this reason, it is often useful to have regard to the same types of statistical/evidentiary issues that will arise in confirmatory testing, though for a different reason. The main deficiency of stepwise methods in selection of variables is that it can travel through idiosyncratic paths that miss sets of explanatory variables with high evidence of a relationship to the response variable. This is why comparisons like the all-possible-models method are considered preferable to stepwise methods.
Assuming you have sufficient computational power to do so, I would recommend you conduct exploratory analysis by computing the goodness-of-fit statistics for all possible models and then examining those models that should high levels of fit relative to the number of model parameters. This method is more likely to identify models with true hypotheses, and unlike the stepwise procedure, it is more systematic and will not miss important models. Since this is exploratory analysis, you should also allow yourself to be guided by exogenous concerns about what hypotheses/models are "interesting" in the context of your field, what are the costs of collecting data, etc., but you can use the all-possible-models method to augment this. This latter method will give more systematic statistical information on your exploratory data than stepwise methods.
Finally, you say that hypotheses generated by the stepwise method are "shaky". It is okay for hypotheses generated in the exploratory phase to be shaky, because the whole point is that you are only generating tentative hypotheses for later testing and confirmation. Indeed, arguably all hypotheses generated in the exploratory phase are and ought to be "shaky". The reason to prefer all-possible-models over stepwise methods is that it more systematically identifies hypotheses supported in the explanatory phase.