Yikes! All these workarounds have led me to the conclusion that the HTML checkbox kind of sucks if you want to style it.
As a forewarning, this isn't a CSS implementation. I just thought I'd share the workaround I came up with in case anyone else might find it useful.
I used the HTML5 canvas element.
The upside to this is that you don't have to use external images and can probably save some bandwidth.
The downside is that if a browser for some reason can't render it correctly, then there's no fallback. Though whether this remains an issue in 2017 is debatable.
Update
I found the old code quite ugly, so I decided to give it a rewrite.
Object.prototype.create = function(args){
    var retobj = Object.create(this);
    retobj.constructor(args || null);
    return retobj;
}
var Checkbox = Object.seal({
    width: 0,
    height: 0,
    state: 0,
    document: null,
    parent: null,
    canvas: null,
    ctx: null,
    /*
     * args:
     * name      default             desc.
     *
     * width     15                  width
     * height    15                  height
     * document  window.document     explicit document reference
     * target    this.document.body  target element to insert checkbox into
     */
    constructor: function(args){
        if(args === null)
            args = {};
        this.width = args.width || 15;
        this.height = args.height || 15;
        this.document = args.document || window.document;
        this.parent = args.target || this.document.body;
        this.canvas = this.document.createElement("canvas");
        this.ctx = this.canvas.getContext('2d');
        this.canvas.width = this.width;
        this.canvas.height = this.height;
        this.canvas.addEventListener("click", this.ev_click(this), false);
        this.parent.appendChild(this.canvas);
        this.draw();
    },
    ev_click: function(self){
        return function(unused){
            self.state = !self.state;
            self.draw();
        }
    },
    draw_rect: function(color, offset){
        this.ctx.fillStyle = color;
        this.ctx.fillRect(offset, offset,
                this.width - offset * 2, this.height - offset * 2);
    },
    draw: function(){
        this.draw_rect("#CCCCCC", 0);
        this.draw_rect("#FFFFFF", 1);
        if(this.is_checked())
            this.draw_rect("#000000", 2);
    },
    is_checked: function(){
        return !!this.state;
    }
});
Here's a working demo.
The new version uses prototypes and differential inheritance to create an efficient system for creating checkboxes. To create a checkbox:
var my_checkbox = Checkbox.create();
This will immediately add the checkbox to the DOM and hook up the events. To query whether a checkbox is checked:
my_checkbox.is_checked(); // True if checked, else false
Also important to note is that I got rid of the loop.
Update 2
Something I neglected to mention in the last update is that using the canvas has more advantages than just making a checkbox that looks however you want it to look. You could also create multi-state checkboxes, if you wanted to.
Object.prototype.create = function(args){
    var retobj = Object.create(this);
    retobj.constructor(args || null);
    return retobj;
}
Object.prototype.extend = function(newobj){
    var oldobj = Object.create(this);
    for(prop in newobj)
        oldobj[prop] = newobj[prop];
    return Object.seal(oldobj);
}
var Checkbox = Object.seal({
    width: 0,
    height: 0,
    state: 0,
    document: null,
    parent: null,
    canvas: null,
    ctx: null,
    /*
     * args:
     * name      default             desc.
     *
     * width     15                  width
     * height    15                  height
     * document  window.document     explicit document reference
     * target    this.document.body  target element to insert checkbox into
     */
    constructor: function(args){
        if(args === null)
            args = {};
        this.width = args.width || 15;
        this.height = args.height || 15;
        this.document = args.document || window.document;
        this.parent = args.target || this.document.body;
        this.canvas = this.document.createElement("canvas");
        this.ctx = this.canvas.getContext('2d');
        this.canvas.width = this.width;
        this.canvas.height = this.height;
        this.canvas.addEventListener("click", this.ev_click(this), false);
        this.parent.appendChild(this.canvas);
        this.draw();
    },
    ev_click: function(self){
        return function(unused){
            self.state = !self.state;
            self.draw();
        }
    },
    draw_rect: function(color, offsetx, offsety){
        this.ctx.fillStyle = color;
        this.ctx.fillRect(offsetx, offsety,
                this.width - offsetx * 2, this.height - offsety * 2);
    },
    draw: function(){
        this.draw_rect("#CCCCCC", 0, 0);
        this.draw_rect("#FFFFFF", 1, 1);
        this.draw_state();
    },
    draw_state: function(){
        if(this.is_checked())
            this.draw_rect("#000000", 2, 2);
    },
    is_checked: function(){
        return this.state == 1;
    }
});
var Checkbox3 = Checkbox.extend({
    ev_click: function(self){
        return function(unused){
            self.state = (self.state + 1) % 3;
            self.draw();
        }
    },
    draw_state: function(){
        if(this.is_checked())
            this.draw_rect("#000000", 2, 2);
        if(this.is_partial())
            this.draw_rect("#000000", 2, (this.height - 2) / 2);
    },
    is_partial: function(){
        return this.state == 2;
    }
});
I modified slightly the Checkbox used in the last snippet so that it is more generic, making it possible to "extend" it with a checkbox that has 3 states. Here's a demo. As you can see, it already has more functionality than the built-in checkbox.
Something to consider when you're choosing between JavaScript and CSS.
Old, poorly-designed code
Working Demo
First, set up a canvas
var canvas = document.createElement('canvas'),
    ctx = canvas.getContext('2d'),
    checked = 0; // The state of the checkbox
canvas.width = canvas.height = 15; // Set the width and height of the canvas
document.body.appendChild(canvas);
document.body.appendChild(document.createTextNode(' Togglable Option'));
Next, devise a way to have the canvas update itself.
(function loop(){
  // Draws a border
  ctx.fillStyle = '#ccc';
  ctx.fillRect(0,0,15,15);
  ctx.fillStyle = '#fff';
  ctx.fillRect(1, 1, 13, 13);
  // Fills in canvas if checked
  if(checked){
    ctx.fillStyle = '#000';
    ctx.fillRect(2, 2, 11, 11);
  }
  setTimeout(loop, 1000/10); // Refresh 10 times per second
})();
The last part is to make it interactive. Luckily, it's pretty simple:
canvas.onclick = function(){
  checked = !checked;
}
This is where you might have problems in IE, due to their weird event handling model in JavaScript.
I hope this helps someone; it definitely suited my needs.