Eu nunca tinha andado de um avião should also be acceptable
The sentence doesn't make sense in English anyway. I wanted to "montado" the plane, like a horse, but I knew they wouldn't accept it. But you wouldn't "ride a plane" in English, either. Maybe ride in a plane.
Very few people have "ridden a plane". I have seen it at air shows, when someone rides standing on the wing of a biplane, very slow in flight, and obviously with a harness.
no... you can use "em um", "num" (em+um), "de", but not "de um".
So andado can mean walked, thought, ridden, travelled, and been? And that's just so far.
Should be 'traveled' or 'taken' a plane rather than 'ridden.'