Liquid: Can I get a random element from an Array

It cannot be done without a plugin or custom function. Although, there is an ongoing effort to implement this in the next releases: https://github.com/Shopify/liquid/pull/101 and then it would look like:

{% for tag in site.tags order:ascending %} 
   ...
{% endfor %}

{% for category in site.categories %}
    {% assign catg_name = category.first %}
    {% if catg_name == page.category %}
        {% assign catg_posts = category.last %}
    {% endif %}
{% endfor %}
{% for post in catg_posts %}
    {% if post.title == page.title %}
        {% unless forloop.last %}
            {% assign next = catg_posts[forloop.index] %}
            <li class="previous">
            <a href="{{ site.baseurl }}{{ next.url }}">&larr;{{ next.title }}</a>
            </li>
        {% endunless %}
        {% unless forloop.first %}
            <li class="next">
            <a href="{{ site.baseurl }}{{ prev.url }}">{{ prev.title }}&rarr;</a>
            </li>
        {% endunless %}
    {% endif %}
    {% assign prev = post %}
{% endfor %}

As you have mentioned you can save and use the previous iteration value for the previous post link( in my case I use it as the next post link since I don't want the default newest-first order ). For the next array element you can use forloop.index. This is the 1-based index of the for loop and will give you the next item of a zero-based array.