I've never set up google ads before, but you mentioned you only have it on the front page. You said that you'd need to have it on All the generated pages to be worth it, but I've got an alternative suggestion.
Do you know what the most popular generated pages are ? put it on the top 10 of those ?
then maybe put some on the hot items, and unusual deals pages ?
again. I've no idea how easy / hard this would be to do, I apologize if it's a logistical nightmare.