I have been pulled aside by security ("SSSS" code on my boarding pass) when going from the Schengen to non-Schengen zone on my way to the US via Keflavík. I had my bags inspected, I was swabbed for residue, etc. The whole procedure took less than 10 minutes.
I would recommend heading to your gate first to make sure you have time, and then find a place to eat. As Jacob says in his answer, there is food available in both the Schengen and non-Schengen zones of the airport. I'd rather be hungry than miss my flight.
Finally, food is available on Icelandair flights, but it's not free. You can a use credit/debit card or Saga points, but they do not accept cash on board. If you pre-order your meal, you get a 20% discount.