I understand what you say, although I still feel "without me being" sounds fine. But what happens with this?
"without one being warned"

That seems to be correct. Shouldn't it be "without one's being warned", like in "without one's permission"?

What about these?
1a) You can drive with me being your navigator.
1b) You can drive without me being your navigator.
2a) You can drive with my being your navigator.
2b) You can drive without my being your navigator.

I again feel both 1 are correct and 2 sound weird. Thanks!