I will not go into describing code (hint- you need the "micros()" function,) but given your specifications, you clearly cannot use PWM to control the LED brightness. The closest you might get would be to control the pulse duration, perhaps using a timer.
If you know how many steps of brightness you need, you can use more than one output pin to power the LED through different resistors in a binary representation.
In meantime I found a sketch in the Arduino cookbook which is very useful for my approach. This sketch employes the timer1 library. I wonder whether it is possible to add a second LED at different frequency and pulse duration to the code? Or is Timer1 limited to one LED?
Here is the sketch:
#include <TimerOne.h> #define pwmRegister OCR1A // the logical pin, can be set to OCR1B
const int outPin = 9; // the physical pin
long period = 10000; // the period in microseconds
long pulseWidth = 1000; // width of a pulse in microseconds
int prescale[] = {0,1,8,64,256,1024}; // the range of prescale values