Buy a new grill.
Put a tarp down first.
Use lighter fluid to clean the grates.