Coarse-grained (lattice-) models have a long tradition in aiding efforts to decipher the physical or biological complexity of proteins. Despite the simplicity of these models, however, numerical simulations are often computationally very demanding and the quest for efficient algorithms is as old as the models themselves. Expanding on our previous work [T. Wüst and D. P. Landau, Phys. Rev. Lett. 102, 178101 (2009)], we present a complete picture of a Monte Carlo method based on Wang-Landau sampling in combination with efficient trial moves (pull, bond-rebridging, and pivot moves) which is particularly suited to the study of models such as the hydrophobic-polar (HP) lattice model of protein folding. With this generic and fully blind Monte Carlo procedure, all currently known putative ground states for the most difficult benchmark HP sequences could be found. For most sequences we could also determine the entire energy density of states and, together with suitably designed structural observables, explore the thermodynamics and intricate folding behavior in the virtually inaccessible low-temperature regime. We analyze the differences between random and protein-like heteropolymers for sequence lengths up to 500 residues. Our approach is powerful both in terms of robustness and speed, yet flexible and simple enough for the study of many related problems in protein folding.