A form of FSK called phase−coherent Frequency Shift Keying was used in the mostly defunct IEEE 802.4, aka token bus. There were actually several flavors of token bus:
- using phase-continous FSK it ran up to 1Mbit on 75-ohm coax
- using phase-coherent FSK it ran up to 10Mbit on something [to be determined]
- there was a third version using AM/PSK (amplitude modulation and phase shift)
In the phase-coherent form the frequency transitions are made only at zero-crossings, but I'm not sure what the additional titbid that "the two singalling frequencies are integrally related to the data rate" means. You can probably read US patent 4799239 and figure that out.
Also, what you are asking about in your second paragraph is not just FSK (as used in the ancient modems) but MFSK, also called M-ary FSK. I suppose one could use this to code multiple bits, like [say] Gigabit Ethernet does with its 5 voltage levels over twisted pairs [1000BASE-T]. Given the general death of FSK over cables though, I'm not sure this was ever done [in commercial products]. Google Scholar is your friend for finding more or less obscure academic attempts at practical products and theoretical background on it.
I don't remember exactly what caused the demise of FSK in modems (and transition to PSK etc. after the 2400 baud ones), but a certain cheekily titled paper notes with respect to the [wireless] 802.11 protocol that:
FSK was abandoned in favor of QAM when the 802.11 standards committee deemed it impossible to implement in 1997. This was mainly due to the limitations of the technology available at the time, one of which is the poor tracking bandwidth of the traditional Phase Locked Loop (PLL). The second issue was due to the numerous noise sources associated with down conversion (dominant channel noises).
So you may need more expensive electronics for high-speed MFSK.
Also from this textbook
Binary and M-ary FSK have the poorest bandwidth efficiency of all the digital modulation techniques used.
Efficiency is on the horizontal axis in the following graph (from the same book); the vertical axis there is the power required to get a BER of 10^-4. So, on the plus side, FSK is thrifty in terms of transmitter energy/power requirements.
After reading Andy's answer, I realize that you may have been thinking just in broad terms of using sub-carriers, i.e. frequency division multiplexing in your 2nd paragraph. But [M]FSK is not one of those schemes.