I was looking for the same thing a while ago, and came across this video course called "Hana Hana Hangul":
https://www.youtube.com/watch?v=KN4mysljHYc
It's a native speaker, teaching in English, with essentially no Romanization (other than occasional brief explanations for individual letter sounds). The first few lessons are free, the rest are available on KoreanClass101.com.
I have no affiliation with KoreanClass101.com other than as a customer. You can sign up for free and get limited access, and they will send you emails offering upgrades. After holding out for a few weeks, they offered me a deal of about $35 for two years of basic access, which I signed up for and have been happy with.