Tourist visas don't exist for KSA. Only in 2015 did someone from the government announce there were no intentions to start them. Although with the oil prices slumping, maybe they will introduce them in the future.

As for Madain Saleh, I wouldn't bother, it's not overly interesting, particularly when compared to Petra, and as mentioned, very out of the way. Al Ula does indeed have an airport with flights from Riyadh and Jeddah, but Medinah is the closest main alternative or Jeddah at a push.

I visited whilst working out there as part of a road trip from Riyadh so can't comment much about flights, but as for the visa, well, I've known a couple of people to try and go via agencies but without much luck alas.