Is it possible to alter a CSS stylesheet using JavaScript? (NOT the style of an object, but the stylesheet itself)

As of 2011

Yes you can, but you will be facing cross-browser compatibility issues:

http://www.quirksmode.org/dom/changess.html

As of 2016

Browser support has improved a lot (every browser is supported, including IE9+).

• The insertRule() method allows dynamic addition of rules to a stylesheet.

• With deleteRule(), you can remove existing rules from a stylesheet.

• Rules within a stylesheet can be accessed via the cssRules attributes of a stylesheet.

We can use a combination of .insertRule and .cssRules to be able to do this all the way back to IE9:

function changeStylesheetRule(stylesheet, selector, property, value) {
    // Make the strings lowercase
    selector = selector.toLowerCase();
    property = property.toLowerCase();
    value = value.toLowerCase();

    // Change it if it exists
    for(var i = 0; i < s.cssRules.length; i++) {
        var rule = s.cssRules[i];
        if(rule.selectorText === selector) {
            rule.style[property] = value;
            return;
        }
    }

    // Add it if it does not
    stylesheet.insertRule(selector + " { " + property + ": " + value + "; }", 0);
}

// Used like so:
changeStylesheetRule(s, "body", "color", "rebeccapurple");

Demo

When I want to programmatically add a bunch of styles to an object, I find it easier to programmatically add a class to the object (such class has styles asscociated with it in your CSS). You can control the precedence order in your CSS so the new styles from the new class can override things you had previously. This is generally much easier than modifying a stylesheet directly and works perfectly cross-browser.