Because DefaultTableCellRenderer is JLabel, you can use it's text alignment properties in a custom renderer to label the icon. The example below overrides getRowHeight() to ensure visibility. I've updated the example to use a custom class, as suggested here; an instance of LabelIcon holds an icon and label pair for each row.

import java.awt.*;
import javax.swing.*;
import javax.swing.table.*;
/**
 * @see https://stackoverflow.com/a/36830558/230513
 */
public class TableExample {
    private JFrame frame = new JFrame("Table Demo");
    private Icon errorIcon = (Icon) UIManager.getIcon("OptionPane.errorIcon");
    private Icon infoIcon = (Icon) UIManager.getIcon("OptionPane.informationIcon");
    private Icon warnIcon = (Icon) UIManager.getIcon("OptionPane.warningIcon");
    private String[] columnNames = {"String", "Icon"};
    private Object[][] data = {
        {"One", new LabelIcon(errorIcon, "Error")},
        {"Two", new LabelIcon(infoIcon, "Information")},
        {"Three", new LabelIcon(warnIcon, "Warning")},
        {"Four", new LabelIcon(errorIcon, "Error")},
        {"Five", new LabelIcon(infoIcon, "Information")},
        {"Six", new LabelIcon(warnIcon, "Warning")}};
    private final TableModel model = new DefaultTableModel(data, columnNames) {
        @Override
        public Class<?> getColumnClass(int column) {
            switch (column) {
                case 0:
                    return String.class;
                case 1:
                    return LabelIcon.class;
                default:
                    return String.class;
            }
        }
    };
    private static class LabelIcon {
        Icon icon;
        String label;
        public LabelIcon(Icon icon, String label) {
            this.icon = icon;
            this.label = label;
        }
    }
    private static class LabelIconRenderer extends DefaultTableCellRenderer {
        public LabelIconRenderer() {
            setHorizontalTextPosition(JLabel.CENTER);
            setVerticalTextPosition(JLabel.BOTTOM);
        }
        @Override
        public Component getTableCellRendererComponent(JTable table, Object
            value, boolean isSelected, boolean hasFocus, int row, int col) {
            JLabel r = (JLabel) super.getTableCellRendererComponent(
                table, value, isSelected, hasFocus, row, col);
            setIcon(((LabelIcon) value).icon);
            setText(((LabelIcon) value).label);
            return r;
        }
    }
    public TableExample() {
        JTable table = new JTable(model) {
            @Override
            public int getRowHeight() {
                return super.getRowHeight() + infoIcon.getIconHeight();
            }
            @Override
            public Dimension getPreferredScrollableViewportSize() {
                return new Dimension(
                    (5 * super.getPreferredSize().width) / 4,
                    4 * this.getRowHeight());
            }
        };
        table.setAutoCreateRowSorter(true);
        table.setDefaultRenderer(LabelIcon.class, new LabelIconRenderer());
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(new JScrollPane(table));
        frame.pack();
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
    }
    public static void main(String[] args) {
        EventQueue.invokeLater(() -> {
            TableExample tableExample = new TableExample();
        });
    }
}