Can random be used for ordering with related/assets, in cached code?
What about composing a custom Twig array containing all the data you need. This does all your DB queries and because you write it in default sort order (randomize afterwards), you can cache all the heavy lifting of your template: 

{# Cache an array of fake "ElementModels" #}
{% cache %}

{% set imagesArray = [] %}
{% set tagsColor = [] %}

{% for image in craft.assets %}

    {% for tag in image.tagsColor %}

        {% set tagColor = {
            slug: tag|slugify,
            tag: tag,
        } %}

        {% set tagsColor = tagsColor|merge(tagColor) %}

    {% endfor %}

    {% set imageObject = {
        url: image.url,
        title: image.title,
        tagsColor: tagsColor,
    } %}

    {% set imagesArray = imagesArray|merge(imageObject) %}

{% endfor %}

{% endcache %}


Then randomize your images and print the JSON:

{# Randomize our array #}
{% set imagesArray = shuffle(imagesArray) %}

{# Print the thing into our JSON #}
{% for image in imagesArray %}
    ...
{% endfor %}