Nice Question (Rated 5 stars)...
I have learnt a lot while working this out...
For this you can use the GridView's PagerTemplate
] property. (The link here has an example that does close to what you want...).
You just have to write the controls you need inside PagerTemplate
Do also check another example at PagerTemplate not showing in GridView