I assume you create a PhysicsConnector
to connect between your sprites and bodies. Create a list of these physics connectors, and when you decide you should remove a body (And its sprite), do the following:
Body bodyToRemove = //Get it from your contact listener
for(PhysicsConnector connector : mPhysicsConnectors) //mPhysicsConnectors is the list of your coins physics connectors.
if(connector.getBody() == bodyToRemove)
removeSpriteAndBody(connector); //This method should also delete the physics connector itself from the connectors list.
About sprites organization: Coins are re-useable sprite, you shouldn't recreate them every time. You can use an object pool, here's a question about this topic.