See, even hierarchical clustering needs parameters if you want to get a partitioning out. In fact, hierarchical clustering has (roughly) four parameters: 1. the actual algorithm (divisive vs. agglomerative), 2. the distance function, 3. the linkage criterion (single-link, ward, etc.) and 4. the distance threshold at which you cut the tree (or any other extraction method).
Fact is that there doesn't exist any good "push button" solution to cluster analysis. It is an explorative technique, meaning that you have to try different methods and parameters and analyze the result.
I found DBSCAN to be very usable in most cases. Yes, it has two parameters (distance threshold aka: neighbor predicate, and minpts aka core predicate) - I'm not counting the distance function separately this time, because it's really a "is neighbor of" binary predicate that is needed; see GDBSCAN.
The reason is that in many applications you can choose these values intuitively if you have understood your data well enough. E.g. when working with Geo data, distance is literatlly in kilometers, and it allows me to intuitively specify the spatial resolution.
Similarly, minpts gives me an intuitive control over how "significant" a subset of observations needs to be before it becomes a cluster.
Usually, when you find DBSCAN hard to use, it is because you have not understood "distance" on your data yet. You then first need to figure out how to measure distance and what the resulting numbers mean to you. Then you'll know the threshold to use.
And in the end go and try out stuff. It's data exploration, not "return(truth);". There is not "true" clustering. There are only "obvious", "useless" and "interesting" clusterings, and these qualities cannot be measured mathematically; they are subjective to the user.
You can find plenty of discussion on kmeans with binary variables here in the stack exchange network.
Binary variables are less of a problem for DBSCAN because it does not minimize least squares, it does not compute the mean, and it can be used with arbitrary measures such as Jaccard distance for binary variables (it even can be used with similarities, non-metric measures, kernels, etc.)
But that doesn't mean the data will just work. If you have binary variables there probably is no good choice of epsilon. Because there won't be small values. If you consider Hamming distance, if epsilon is larger than 1 (i.e. it allows one variables to be different), you probably already get everything connected. That is due to a lack of "resolution" in the data itself, and probably not to be solved by the algorithm or distance.
Correlated binary attributes like male/female put double weight on this parameter. That is probably not desirable.
There are many, many extensions of DBSCAN. I'm pretty sure there is one for categorical data. I know there is PreDeCon for axis aligned subspaces, and something like 4C or so for correlated continuous attributes. So you will have to do some research on what has been published. Don't assume a software package contains all that there is.
Best Answer
The only measure that I know that takes noise points and density into account is DBCV:
I haven't used it though.