What is the best way to implement ajax based pagination on custom query based templates?

Soumitra Chakraborty wrote a very good tutorial on Getting Started with AJAX & WordPress Pagination. I would recommend following that pattern (in terms of how to use admin_ajax.php in conjunction with your functions.php.

That tutorial will give you a great framework for how to implement ajax pagination by hand.

In terms of your own specific requirements for a custom query (which it sounds like might involve getting data from non-standard tables) you can use the WP_Query class to do some pretty advanced stuff (like what you describe) in your custom function that you define in functions.php.