How can I choose and change a post title at random from an array when it is published?

You could randomize the array with array_rand which will return the key, and then use array_flip to switch the key with the value (ie get your random title).

Hook into save_post, so the random title is assigned and update the DB when you actually publish a post as opposed to using the_title filter.

function save_title( $post_id ){

    global $wpdb;

    $title = array (
        '1' => 'another title',
        '2' => 'here is again, a title',
        '3' => 'random titles',
        '4' => 'RANDOM TITLE',
        '5' => 'ANOTHER RanDom TiTlE!',
        '6' => 'titles everywhere'
    );

    $wpdb->update( $wpdb->posts, 
        array( 'post_title' =>  array_rand( array_flip( $title ) ) ),
        array( 'ID' => $post_id ) ); 
}

add_action( 'save_post', 'save_title');