Again I am REALLY surprised I have not turned up any pre-existing libraries for such a thing,
Why? Do you like doing things other people have done?
Clearly it is a solved problem based on Reprap printers everywhere using steppers.
There are many solutions in the RepRap world, why does everything have to be a library?
How do I get a continous pulse train coming off the arduino of variable frequency, without blocking everything else?
You use a timer to generate regular interrupts and then in the interrupt service routine you can either step every time it is entered and control the speed through altering the frequency of the timer.
OR
Increment a 16 bit counter with some value and only step when the counter overflows a certain bit, like when the most significant byte changes. That way you get to control the speed by changing the increment value.
I need to control 2 stepper motors, speed only not elapsed steps
You have no choice, it is a stepping motor, you control the steps. It sounds like you have the wrong sort of motor for your project.