Useful links: http://codex.wordpress.org/Function_Reference/paginate_links, http://codex.wordpress.org/Making_Custom_Queries_using_Offset_and_Pagination
Try something like this
<ul class="posts_list">
<?php
$paged = ( get_query_var( 'paged' ) ) ? get_query_var( 'paged' ) : 1;
$ppp = 4;
$offset = 1;
//Manually determine page query offset (offset + current page (minus one) x posts per page)
$page_offset = $offset + ( ($paged - 1) * $ppp );
$query = new wp_query(array(
'offset' => $page_offset,
'posts_per_page' => $ppp,
'cat' => $cat_id,
'paged' => $paged
));
if ($query->have_posts()) : while ($query->have_posts()) : $query->the_post(); ?>
<li>
<a href="<?php the_permalink(); ?>"><?php the_post_thumbnail( 'catmed' ); ?></a>
<a href="<?php the_permalink(); ?>" rel="bookmark"> <?php the_title(); ?> </a>
</li>
<?php endwhile; else: ?><?php endif; ?>
</ul>
<?php
// pagination
$big = 999999999; // need an unlikely integer
echo paginate_links(array(
'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
'total' => ceil(($query->found_posts - $offset) / $ppp),
'format' => '?paged=%#%',
'current' => max( 1, get_query_var('paged') ),
));
wp_reset_query();
?>