Caching variables for use elsewhere in a template?
Update: This doesn't work. Leaving it here temporarily in case it helps generate more ideas.

Haven't tried this myself, but you might try returning all testimonials and then use twigs random method to select one after the fact.

{% cache %}

    {% set myField = entry.myMatrixField %}

    {% for block in myField %}
        {% if block.type == "someType" %}
            {% set presentationCode %}
                ...Presentation code
            {% endset %}
        {% elseif block.type == "someType" %}
            {% set presentationCode %}
                ...Presentation code
            {% endset %}
        {% elseif block.type == "someType" %}
            {% set randomEntry = craft.entries.section("testimonials").find() %}
        {% endif %}
    {% endfor %}

{% endcache %}

{% if randomEntry %}
    {% set randomEntry = random(randomEntry) %}
    {% set presentationCode %}
        ...Presentiaon code
    {% endset %}
{% endif %}

{{ presentationCode }} 


Note: I suspect that you will need the .find() on the end of the ElementCriteriaModel statement so that it gets converted to an array.

Update: To do this you will also probably need to place all your presentation code in a variable and then display later in the template.