You are correct in that you need an inner product to define the cross product. A geometric picture of it is as follows: take two vectors in three dimensions. They determine a parallelogram and the cross product is defined to be the vector perpendicular (with respect to the inner product) to the parallelogram and with magnitude equal to its area.
Note that there is something special in 3-dimensions that allows this definition to work, namely that to any plane there is a unique perpendicular direction. This is not the case in other dimensions so this definition does not generalize. Indeed, as the wikipedia article states, the only other dimension that has an analogous cross product is 7 (dimension 1 also has a cross product but it is trivial-- just negative of the regular product of real numbers). What is special about dimensions 1,3 and 7 is that there are division algebras only in dimensions 2,4, and 8 (the real numbers, the quaternions, and the octonions). The wikipedia article talks more about this construction.