I've done a custom theme now the client want to be able to upload a different header image for each page within the back-end of WP. Does a plugin exist for this or what custom coding would I need to do.
Take a look at WordPress custom header feature: http://codex.wordpress.org/Custom_Headers . This could be definitely a good start in your problem. Is not hard to implement and is easy to use by your client.