So there you go: the target audience has grown by one.
I've tried google ads, i've tried engaging on forums, but nothing seems to get anywhere. Any suggestions appreciated!
Problem with the search network is that you need to target people who match your offing closely and it's very hard to do that when you don't know if the user 1) has an iPhone, 2) cooks, and 3) wants help deciding what to cook. So a normal 1% clickthrough rate would likely end up much lower than that unless you hit on some awesome uncompetitive keywords that match exactly what your app does, for the right target market.
At least with the content network, you can target foodies, and maybe some pages mention iphones and recipes so you can target those accurately. Some work involved, but that's how I'd do it.
Other thoughts:
You're calling it Random Chef. That doesn't reaaally solve the problem of the user. A casual scanner might think 'throw in random ingredients' or make some similar non-connection to what the app does. Their problem (or solution) isn't 'randomness', it's deciding what to make. So maybe 'menu decision maker' or 'recipe suggestion box' or 'chef's recipe suggestions' or something that a person who is reading a list of app names says 'that's exactly what I need!' because it hints at solving the problem they have.
Another thought: maybe the 'benefit' isn't the decision making, it's the more interesting menu. I know people who will order the same things from the store each week just so they don't have to think about it. That'll get boring after a while, so your app helps to make it less boring. Maybe add a checkbox for 'standard' recipes, and those make up the bulk of the recipes each week so everybody is happy, and throw in a new one once/twice a week just to grow the collection without making them think through each meal every day.
In any case, your idea of 1-month apps is a great one. Nice work!
Anyway, if I think of a better response/solution than "it is what it is", I will be sure to let you know. Good luck in the mean time.
Now I'm tempted to go write my own webapp to do that, lol :D