Actually, it turns out that you can't have it 'both ways': if your intention is to not have any sense of 'absolute orientation' on the sphere (that is, if the players aren't always e.g. facing towards the poles), then you'll need to have a notion of player orientation. This is because, contrary to what intuition might suggest, movement on the sphere is not exactly like movement on a plane, not even locally (quite); the intrinsic curvature of the sphere means that players can take actions that will rotate themselves!
For the most extreme example of what I'm talking about, imagine that the player starts at a point on the equator (for convenience we'll imagine a clock face mapped onto the equator from above, and put the player at 6 o'clock), facing 'up' - that is, towards the North Pole. Suppose the player walks all the way to the North Pole; then they'll be facing directly towards the 12 o'clock point. Now, let the player move directly to their right, from the North Pole back to the equator; they'll wind up at the 3 o'clock point - but because their facing doesn't change when they move right (the idea is that their facing doesn't change no matter how they move), they'll still be facing the 12 o'clock point - they're now facing along the equator! Now, let them move 'backwards' back to their starting (6 o'clock) point; then they'll still be facing along the equator, so they'll be facing towards the 3 o'clock point - just moving along the sphere without ever changing their 'personal' orientation has caused them to rotate from facing towards the north pole to facing along the equator! In a sense, this is an elaboration of the old 'a hunter moves a mile south, a mile west and then a mile north' joke - but here we're taking advantage of the curvature of the sphere to effect a change of direction. Note that the same effect still happens even on much smaller scales; this is the most extreme version of it, but even just short 'one foot north, one foot east, one foot south, one foot west' rectangles won't leave the player facing precisely the way they were before - this is an expression of the fact that the sphere has nontrivial curvature.
Fortunately, quaternions do (as you noted yourself) handle this situation; since a quaternion represents an arbitrary rotation, it effectively represents an arbitrary 'point plus orientation' on the sphere: imagine starting with a 'triaxis' at the origin and giving it some arbitrary rotation, then moving one unit in whichever direction the rotated axes' Z-axis points; a little thought will convince you that this brings you to a point on the unit sphere with some 'orientation' (i.e., some arrangement of the X and Y axes of your triaxis), and that you can get to every point+orientation on the unit sphere this way (just assign your Z axis to point along the line from the origin through your point on the sphere, then transport your triaxes back to the origin along that line). What's more, since multiplication of quaternions corresponds to composition of rotations, each of the operations you describe can be represented by multiplying your 'current orientation' by an appropriately-chosen quaternion: specifically, since the (unit) quaternion (qx,qy,qz,qw) means 'rotate about the (qx,qy,qz) axis by arccos(qw)', then (depending on your specific choice of coordinate system, and letting c_a be cos(alpha) and s_a be sin(alpha)) two of the three quaternions M_x = (s_a, 0, 0, c_a), M_y = (0, s_a, 0, c_a), and M_z = (0, 0, s_a, c_a) will represent 'rotate (i.e. move) in the direction I'm currently facing by alpha' and 'rotate in a direction orthogonal to the one I'm currently facing by alpha'. (The third of those quaternions will represent 'rotate my character about his own axis') This means that every tick you'll figure out which key has been pressed and then, e.g., say
Cur_q = M_x * Cur_q if the player has pressed up, or
Cur_q = M_y * Cur_q if the player pressed right (or possibly something like
Cur_q = M_yinv * Cur_q if the player pressed left, where M_yinv is the 'inverse' of the M_y quaternion, representing a rotation the other way). Note that you have to be careful which 'side' you apply the rotation on, whether to premultiply or postmultiply; to be frank, it may be easiest to solve that with trial-and-error, trying both multiplications and seeing which works.
Going from your updated quaternion to a point on the sphere (and to an orientation of your character) is relatively straightforward, too: by the correspondence of the last paragraph, all you have to do is use your quaternion on the basis vectors (1,0,0), (0,1,0) and (0,0,1) of your frame via 'rotate vector by quaternion' operation v → qvq-1 (where the multiplications here are quaternion multiplies and we identify the vector v=(x,y,z) with the 'degenerate quaternion' (x,y,z,0)). For instance, the position on the unit sphere is gotten by just transforming the z vector: pos = (qx, qy, qz, qw) * (0, 0, 1, 0) * (-qx, -qy, -qz, qw) = (qx, qy, qz, qw) * (qy, -qx, qw, qz) = (2(qy*qw+qz*qx), 2(qz*qy-qw*qx), (qz^2+qw^2)-(qx^2+qy^2), 0), so
(2(qy*qw+qz*qx), 2(qz*qy-qw*qx), (qz^2+qw^2)-(qx^2+qy^2)) would be the coordinates of the 'transformed' user on the unit sphere (and to get the coordinates on an arbitrary sphere, of course, you'd just multiply those by the sphere's radius); similar calculations work for the other axes, to define e.g. the user's facing direction.