Alter pagination start index
You could do it by implementing hook_url_outbound_alter(), and hook_url_inbound_alter().

With the first hook, you alter the links that are being output from Drupal; you would increase the value of $options['query']['page'].
With the second hook, you alter the links being received from Drupal; you should find the '?page=' string in the URL, and decrease the number after that string.

Keep in mind that $_GET['page'] can be a string like '1,2,4,5,6' if the page has more than one pager. See the code of pager_find_page().  

Also, hook_url_outbound_alter() receive the query parameters in $options, while hook_url_inbound_alter() receives just a string for the URL, which also contains the query part.