How to add a rel attribute to images that contains their categories?

This should work for the rel attribute:

/**
 * Create a rel attribute from the image categories
 *
 * @see http://wordpress.stackexchange.com/a/158024/26350
 */

add_filter( 'get_image_tag', 
    function( $html, $id )
    {
        $rel = array();

        foreach( (array) get_the_category( $id ) as $cat ) 
        { 
            $rel[] = $cat->slug; 
        }

        return str_ireplace( 
            '<img ', 
            sprintf( '<img rel="%s" ', join( ' ', $rel ) ),
            $html
        );
    }
, 10, 2 );

where we use the get_image_tag filter to modify the inserted image HTML.

Ps: I just tested this successfully on my WordPress 3.9.2 install, where I used the following code snippet:

add_action( 'init',
    function()   
    {
        register_taxonomy_for_object_type( 'category', 'attachment' );
    }
);

to activate the categories for attachments.