JSF 2.0: How to override base renderers with custom ones?

Your initial <renderer> declaration looks fine, so I tried it here.

package com.myapp;

import java.io.IOException;

import javax.faces.component.UIComponent;
import javax.faces.context.FacesContext;

import com.sun.faces.renderkit.html_basic.CheckboxRenderer;

public class CustomCheckboxRenderer extends CheckboxRenderer {

    public CustomCheckboxRenderer() {
        System.out.println("CustomCheckboxRenderer <init>");
    }

    @Override
    public void decode(FacesContext context, UIComponent component) {
        System.out.println("CustomCheckboxRenderer decode()");
        super.decode(context, component);
    }

    @Override
    public void encodeBegin(FacesContext context, UIComponent component) throws IOException {
        System.out.println("CustomCheckboxRenderer encodeBegin()");
        super.encodeBegin(context, component);
    }

    @Override
    public void encodeEnd(FacesContext context, UIComponent component) throws IOException {
        System.out.println("CustomCheckboxRenderer encodeEnd()");
        super.encodeEnd(context, component);
    }

}

It works fine. All get printed to stdout. Your problem lies somewhere else. I was using Mojarra 2.0.3 on Tomcat 7.0.5.