The gain of each tube stage is determined at least as much by the circuit as the tube type, too - changing the tube has a lot less effect than altering the circuit, which is why the difference between even a 12AX7 and say a 12AT7 which only has 60% of the gain, doesn't seem to make as much difference as that usually. But for example doubling the value of the plate resistor will double the gain, very nearly - a lot more effective. There is a limit even to that, and you start to affect the tone if you go too far as well, which is why the values used in most amps are within a fairly small range - you won't normally see a plate resistor lower than 47Kohms or higher than 220K, with 100K being by far the most common value.
And way, way more effective than any of this is simply to run a boost pedal in front of the amp - you can easily get 20dB like that, which is equivalent to 100 times as much gain, far beyond anything you can do with the amp.