Well this is partly in my neck of the woods, out of Greece you have two choices, over water to Egypt or over the top, it depends upon your range.
Cross water would be Greece to Alexandria, Alex to Hurghada, Hurghada to Jeddah, Jeddah – Riyadh – Bahrain, Bahrain - Muscat .
Over the top would be Greece to Antalya, Antalya to Amman, Amman to Sharm el Sheikh, Sharm to Jeddah and as above.
These places are used to non scheduled international traffic and customs clearances, I believe you could get avgas at all mentioned.
Avoid Cyprus & Israel at all costs as besides the political/religious angle the place can be expensive.
Investing in Jeppesen to do the planning and send you an enroute kit is more than money well spent.
Don’t think you can cheap it through, spend a little money here and there on handling and your life will be so much easier and you can concentrate on the flying and see part of the world you will not regret…… mind you doing it in a overgrown bongo with 3 chainsaws is an experience all of its own.