I will say, having learned Colemak early on has made me give up on learning vim more than once for the same reason you highlighted -- I want to have my navigation on the homerow but the burden of remapping all of the keys without knowing what I'm doing was too high. I've heard that many people just use hjkl in the standard Colemak positions and don't remap keys at all, but that seems crazy to me, since they are spread all over and J is in the worst possible spot on the keyboard.
But other than that I just learned all the positions from scratch. For me it's not so much the positions I think about, but the mnemonics. For example "d" deletes, so I just have to think "press d", not "press this key in this spot. So learn the new layout and the Vim commands will follow.