Monitoring the concentration of gases in under-ground coal mines is a mandatory process that may save lives. Wireless Sensor Networks (WSNs) can alert mine personnel when dangerous levels of gases are detected, such as methane and carbon monoxide that may cause explosions or poisoning of workers. WSNs must be designed to cover all active mining areas throughout a specified time horizon, thus, posing a trade-off between the cost of installation (i.e., sensors) and operation (i.e., energy consumption). While most literature on node deployment for WSNs in mines focuses on single objective functions, we propose a novel two-stage approach that allows users to address both the cost of installation and the WSN lifetime: in the first stage, our model provides the lowest cost solution that satisfies a user-specified minimum lifetime; in the second stage, the configuration of the WSN is modified in order to maximize its lifetime, subject to maintaining the number of nodes (and, hence, installation costs) from the first stage. Illustrative examples are presented regarding two real coal mines in Boyaca (Colombia).