In seeking environmentally clean technologies, this research has assessed a new alternative to synthesize activated carbon of Colombian mineral coal by using gases from partial combustion of propane (hereafter called flue gases), which are generally exhausted to the atmosphere. The activation was carried out by two methods of synthesis: in the first, pyrolysis was performed prior to activation, while in the second, pyrolysis and activation were carried out simultaneously. This alternative of synthesizing activated carbon was compared with conventional activation of coal using CO2. The activated carbon with flue gases and CO2 were characterized by adsorption of argon at −186 °C, and parameters such as specific surface area, pore size distribution, total pore volume, and micropore volume were determined. The activation with flue gases reduced combustion gas components such as SO2, NOx, and CO2 during the coal activation process. Activation with flue gases resulted in a surface area of 804 m2/g and a total pore volume of 0.38 cm3/g, while activation with CO2 produced a surface area of 1252 m2/g and a total pore volume of 0.43 cm3/g. Subsequently, the application to methane storage was evaluated and found to exceed the reported performance for several commercial carbons with storage factors up to 112.