What best/correct algorithm/procedure to cluster a dataset with a lot 0's?
Maybe I am not understanding your question properly, but k-means clustering is not sensitive to the zeros. More accurately zeros are valid values for features to cluster on. 

While PCA may enable you to reduce the number of features to train on, it may complicate the clarity of the clusters from k-means. PCA may be beneficial in its own right, but AI would resist the urge to feed PCA data into k-means simply to reduce the number of zeros in your data.

HTH