Totally possible, here is a great walkthough: http://bavotasan.com/2010/create-bit-ly-short-urls-for-your-posts-in-wordpress/
Bullet points:
-Write a function that gets the bitly link upon publish
-Remove the default action and add your own
-Call wp_get_shortlink() like normal and bitly will be used