Removing leaflet layers and L.marker method

Use map.removeLayer():

var circle = L.circle([lat, lng], 1000).addTo(map);
map.removeLayer(circle);

Instead of adding all markers directly on the map, you can add the markers on a separate layer (i.e. var markers = new L.FeatureGroup();) and then add that layer on the map (map.addLayer(markers);) outside the loop.

For example,

http://jsfiddle.net/9BXL7/

html

<button>remove all markers</button>
<div id="map"></div>

css

html, body, #map {
    width: 100%;
    height: 100%;
    padding: 0;
    margin: 0;
}

js

var cloudmade = L.tileLayer('http://{s}.tile.cloudmade.com/{key}/997/256/{z}/{x}/{y}.png', {
    maxZoom: 18,
    attribution: 'Map data © 2011 OpenStreetMap contributors, Imagery © 2011 CloudMade',
    key: 'BC9A493B41014CAABB98F0471D759707'
});

var map = L.map('map')
    .setView([50.5, 30.51], 15)
    .addLayer(cloudmade);

var markers = new L.FeatureGroup();

function getRandomLatLng(map) {
    var bounds = map.getBounds(),
        southWest = bounds.getSouthWest(),
        northEast = bounds.getNorthEast(),
        lngSpan = northEast.lng - southWest.lng,
        latSpan = northEast.lat - southWest.lat;

    return new L.LatLng(
    southWest.lat + latSpan * Math.random(),
    southWest.lng + lngSpan * Math.random());
}

function populate() {
    for (var i = 0; i < 10; i++) {
        var marker = L.marker(getRandomLatLng(map));
        marker.bindPopup("<p>Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Donec odio. Quisque volutpat mattis eros. Nullam malesuada erat ut turpis. Suspendisse urna nibh, viverra non, semper suscipit, posuere a, pede.</p><p>Donec nec justo eget felis facilisis fermentum. Aliquam porttitor mauris sit amet orci. Aenean dignissim pellentesque.</p>", {
            showOnMouseOver: true
        });
        markers.addLayer(marker);
    }
    return false;
}

map.addLayer(markers);

populate();
function removeAllMarkers(){
    map.removeLayer(markers);
}
document.querySelector('button').onclick=function(){removeAllMarkers()};

Should you need to DELETE or clear the markers layer to swap out the points in the future use:

markers.clearLayers();