Carbon black (CB) obtained from used car tire rubbers were treated with concentrated sulfuric and nitric acids. The oxidized CB (CB-COO-Na+) is subsequently modified with epichlorohydrin (ECH) and amines including polyethylene imine (PEI). These modified CBs such as CB-PEI are used as metal-free catalysts in methanolysis of sodium borohydride (NaBH4) to produce hydrogen. The hydrogen generation rate (HGR) of 3089 +/- 44.69 mL.min(-1).g(-1) is accomplished at room temperature with CB-PEI-hydrochloric acid (HCl) catalyst. The resulting activation energy of 34.7 kJ/mol for the temperature range of -20 degrees C to +30 degrees C compares favorably to most of alternative catalysts reported in literature while reaction catalyzing capabilities of CB-PEI-HCl particles extend to the subzero temperature range (-20 degrees C-0 degrees C). The reuse and regeneration studies conducted for the CB-PEI-HCl catalyst showed that these catalysts do provide complete conversion at every use up to five consecutive runs and retain 50 +/- 2.5% of the original hydrogen generation rate at the fifth consecutive reuse. The CBs-based catalysts are fully regenerated with HCl treatment.