This study presents the formulation and application of strippable coatings for the entrapment and removal of heavy metals (HMs) and radio nuclides (RNs). The “green” formulations involve the use of a water-based solution consisting of a synthetic biodegradable polymer, polyvinyl alcohol (PVA), together with a natural polymer (sodium alginate) as the polymer matrix and bentonite as the reinforcing agent with cation exchange capacity. Four chelating agents comprising two classical chelating agents (ethylenediaminetetraacetic acid (EDTA), diethylenetriamine-pentaacetic acid (DPTA)) and two “green” chelating agents (iminodisuccinic acid (IDS), 2-phosphonobutane-1,2,4-tricarboxylic acid (PBTC)) were used to evaluate the capacity to remove Cu, Sb, Zn, Sr, Pb, Co, and Hg from the contaminated surfaces. This decontamination method leads to the formation of a solid waste, thus eliminating the need for wastewater treatment. Atomic absorption spectroscopy (AAS), inductively coupled plasma mass spectrometry (ICP-MS), scanning electron microscopy with energy dispersive X-ray spectroscopy (SEM-EDX), and ultraviolet-visible (UV–Vis) spectroscopy were used to comparatively evaluate the decontamination efficacy. EDX elemental mapping confirmed the entrapment of the contaminants inside the polymeric matrix.