REST API: Get body of deleted attachment

If this is a one time export or monthly export that needs to be done, you can use the Monthly Export Service built in to Salesforce. Go to Setup->Data management->Data Export and click "Export Now" or "Schedule Export" and make sure "Include images, documents, and attachments" is checked along with any other data you want to export. Salesforce will export the data, zip it up and e-mail you when the export is available for download.

You can do this using forcetk if you are planning to do this in javascript

here is sample code -

<apex:page docType="html-5.0" title="File Uploader">

Select a file to upload as a new Chatter File.

client.setSessionToken('{!$Api.Session_ID}');

function upload() {
    var file = $("#file")[0].files[0];
    client.createBlob('ContentVersion', {
        Origin: 'H', // 'H' for Chatter File, 'C' for Content Document
        PathOnClient: file.name
    }, file.name, 'VersionData', file, function(response){
        console.log(response);
        $("#message").html("Chatter File created: <a target=\"_blank\" href=\"/" + response.id + "\">Take a look!</a>");
    }, function(request, status, response){
        $("#message").html("Error: " + status);
    });
}

here is internal forcetk implementation for sf blob [link - https://github.com/developerforce/Force.com-JavaScript-REST-Toolkit/blob/master/forcetk.js] -

    /* Low level function to create/update records with blob data
 * @param path resource path relative to /services/data
 * @param fields an object containing initial field names and values for 
 *               the record, e.g. {ContentDocumentId: "069D00000000so2", 
 *               PathOnClient: "Q1 Sales Brochure.pdf"}
 * @param filename filename for blob data; e.g. "Q1 Sales Brochure.pdf"
 * @param payloadField 'VersionData' for ContentVersion, 'Body' for Document
 * @param payload Blob, File, ArrayBuffer (Typed Array), or String payload
 * @param callback function to which response will be passed
 * @param [error=null] function to which response will be passed in case of error
 * @param retry true if we've already tried refresh token flow once
 */
forcetk.Client.prototype.blob = function(path, fields, filename, payloadField, payload, callback, error, retry) { 
    var that = this;
    var url = (this.visualforce ? '' : this.instanceUrl) + '/services/data' + path;
    var boundary = randomString();

    var blob = new Blob([
        "--boundary_" + boundary + '\n' 
        + "Content-Disposition: form-data; name=\"entity_content\";" + "\n" 
        + "Content-Type: application/json" + "\n\n" 
        + JSON.stringify(fields) 
        + "\n\n" 
        + "--boundary_" + boundary + "\n" 
        + "Content-Type: application/octet-stream" + "\n" 
        + "Content-Disposition: form-data; name=\"" + payloadField 
          + "\"; filename=\"" + filename + "\"\n\n",
        payload,
        "\n\n" 
        + "--boundary_" + boundary + "--"
    ], {type : 'multipart/form-data; boundary=\"boundary_' + boundary + '\"'});

    var request = new XMLHttpRequest();
    request.open("POST", (this.proxyUrl !== null && ! this.visualforce) ? this.proxyUrl: url, this.asyncAjax);

    request.setRequestHeader('Accept', 'application/json');
    request.setRequestHeader(this.authzHeader, "Bearer " + this.sessionId);
    request.setRequestHeader('X-User-Agent', 'salesforce-toolkit-rest-javascript/' + this.apiVersion);
    if (this.proxyUrl !== null && ! this.visualforce) {
        request.setRequestHeader('SalesforceProxy-Endpoint', url);
    }

    if (this.asyncAjax) {
        request.onreadystatechange = function() {
            // continue if the process is completed
            if (request.readyState == 4) {
                // continue only if HTTP status is good
                if (request.status >= 200 && request.status < 300) {
                    // retrieve the response
                    callback(request.response ? JSON.parse(request.response) : null);
                } else if(request.status == 401 && !retry) {
                    that.refreshAccessToken(function(oauthResponse) {
                        that.setSessionToken(oauthResponse.access_token, null,oauthResponse.instance_url);
                        that.blob(path, fields, fileName, file, callback, error, true);
                    },
                    error);
                } else {
                    // return status message
                    error(request, request.statusText, request.response);
                }
            }            
        }
    }

    request.send(blob);

    return this.asyncAjax ? null : JSON.parse(request.response);
}