That absolutely is gimbal lock actually, and it's impossible to avoid using Euler angles unless you explicitly have a way to find and use a new up vector to compensate for when the camera is approximately parallel to (0,1,0) i.e. abs(dot(camlook, [0,1,0])) is approximately equal to 1. Just check for that case, and then pick a new "up" vector and calculate your rotation with respect to that vector instead.
Quaternions are a way to avoid this, although you could potentially just use rotation matrices as well and concatenate them. What you'd have to do to use quaternions is to take the camera's angular velocity (technically it isn't really angular velocity but whatever) and represent it as a quaternion. Now, a quaternion is nothing more than a representation of an axis and an angle of rotation, so what you need to do is figure out how many radians (or degrees) the camera rotates every second and then what axis it rotates about. Use these two values to compute a quaternion.
Now, take the camera's initial orientation and represent that as a quaternion also (or use the identity quaternion, which is [0,0,0,1] for [x,y,z,w]). To make rotation happen, all you have to do is multiply the quaternions, however the way you have it represented you would be rotating in some fixed step once per second, which is not smooth at all. There are two ways that you can smooth this out.
The first is that you can instead represent the camera's rotation speed at a smaller unit of time than 1 second, say 1 frame maybe, and then just multiply quaternions. This will work fine if you have a fixed frame rate that never varies and even if it varies a bit, it will probably still look decent.
The other thing you can do is what's called a spherical linear interpolation (SLERP), which is a way of interpolating one quaternion onto another. The way to do this is to take the camera's quaternion and then multiply it by the rotation quaternion as before, and store that in a temporary variable. This will be the position that the camera will be in after 1 second. Now, SLERP interpolates between 0 and 1, and in this case you have the camera's current position, which is at the current time, so no change in time i.e. 0, and then the camera's position after 1 second, so conveniently enough you have those two values, so if you use SLERP and give it a value that is the change in time from the last time you updated, that will allow you to compute a new quaternion, which will be the rotation amount that you want for this frame, and then you just multiply that new quaternion by your camera's current quaternion and you're done.
You ultimately need a rotation matrix though for the camera, but turning a quaternion into a rotation matrix is not particularly difficult (it's just math). Don't forget, if you're orbiting a point that isn't at the origin, you'll need to first do a change of basis on the camera so that it's position/rotation/scale/etc. is in the basis of the object that it's rotating about. If the camera's rotation is independent of the sphere i.e. the sphere is not rotating or if it is rotating, the camera doesn't care about that, then just subtract the sphere's world position from the camera's position, then apply your rotation, then add the sphere's world position back to the camera's position. I don't know what math library you're using, but directx math has the necessary quaternion functions that you'll need including SLERP. If you just want to implement these on your own, you'll have to look up the necessary math but it isn't particularly difficult to do (although it's very hard to actually understand what it's doing and why it works, at least in my opinion).