You mentioned being wary of medications, but have you ever tried taking melatonin? It's a naturally-occurring hormone responsible for sleep and I believe it has helped me, back when I cared.
Now that I know people all over the world, it can actually be advantageous that my sleep schedule is fucked, so I don't really try to fix it anymore ^_^
I think I tried it years ago with no effect. I should probably try it again sometime. It supposedly makes it easier to remember dreams too.