Whole tribes are fighting religious wars over the microcontroller vs. 555 debate. I'm on the microcontroller side.
So the first question is: does it have to be a 555, and what are the arguments for it? (that's two questions.) There may be good reasons for it, but I'd like to know them. "My wife wants me to do it this way" is not a good reason (unless maybe when I see her). Without a good reason I'd have a look at the microcontroller.
The main advantages of the microcontroller are simplicity and accuracy. Simplicity as in you only need a microcontroller and a potmeter to set the duty cycle. Two parts for the complete circuit, or one if your analog control voltage comes from elsewhere in the circuit; then you can drop the potmeter. Accuracy as in 10 bits ADC translates in 10 bit PWM, that's 0.1 % precision at a 1 % accurate clock. Make that a 20 ppm clock if you want to add a crystal. Accuracy is also reproducibility.
OTOH the 555 can work at 15 V if necessary, which the microcontroller can't, and doesn't need programming. The latter is again one of those religious things, but in practice writing a program for this can be done as quickly as designing and calculating the 555 circuit: setup two identical PWM channels but one inverted, the other non-inverted, and in a loop read the ADC and copy the value to both PWM registers.
So the microcontroller outputs complementary signals without external components.
The 555 circuit relies on a capacitor and if you want that at 1 % tolerance you'll pay a few times more than what the microcontroller costs. And even then the frequency will vary with the duty cycle.
All in all there are few 555 applications which a microcontroller can't do better.
Let me preface my answer with a disclaimer: All of my experience PWM'ing motors is with speed control of cooling fans. Your application will certainly differ, at least a little bit.
The way I find the minimum duty cycle, I look for the minimum that will allow the motor to start spinning. With standard muffin fans, this is about 40%. Then I add a small margin just to be safe. I find this by applying 0% duty cycle and slowly ramping it up until the motor starts spinning.
This startup power is higher than the amount of power required to keep the motor spinning once it has already spun up. With fans, this is somewhere in the 20-30% range. In other words, if I wanted to spin a fan really slow, I would have to apply 40% to get it moving and then I could back down to 20-30%.
Normally, just to be safe, I do not go below the startup power. That way I can be sure that the motor is spinning, although it does limit the minimum speed that I can do.
There are problems with this, however. Many things can affect the startup power requirements. Temperature, motor loading, age, dust, different motor lots, etc. You have to take all this into account, and built in some power margin.
Alternatively, you have to monitor your motor through a tachometer or something similar. Then have some motor control software do the appropriate thing if the motor is spinning too fast or too slow. Good motor control software will automatically take into account the startup power and other things.
If you don't want to write motor control software then you have little choice but to empirically measure what the startup power requirement is for your system and then add some more for margin. And hope that you added enough.
Best Answer
Don't.
You can probably do something like that with a very clever combination of 555s, analog filters, extensive measurements, adding analog security measures etc. I haven't fully read Bollock's answer, but I think it nicely illustrates how much knowledge and effectively, trial and error, you'd have to put into a 555-based design. The answer doesn't even scratch real-world trouble you'll enjoy, like component tolerances (especially for larger capacitors) and the resulting behavioral deviations, potential feedback loops, and all that stuff.
It's not worth it. What you describe is the classical use case of microcontrollers, and you already seem to know that. So leave that microcontroller fear behind; any ARM chip or especially Arduino will do what you want for a fraction of the effort and cost of what you're planning to do in analog. ARM eval boards start at below 5€ (this, for example, but I'd recommend you use anything that supports mbed, so these; you're probably best off price/benefit/size-wise using something like this board).
It's really not that hard to program a microcontroller, and I firmly believe in using the right tools for the job. And adjustable PWM is a job for a microcontroller. It also makes it possible to do "smart" things like allowing for emergency breaking with a higher PWM change rate, and also, any microcontroller PWM unit that I know can do 0%–100% duty cycle, not only 5%–95%. Later on, you can combine that with things like battery temperature supervision, that can throttle your motor if the batteries get too hot (that's actually a pretty good feature if you don't like fire but don't want to oversize your batteries too much).
And most interestingly: it would allow you to actually control the speed, assuming you have a sensor for that, in a closed loop control scheme; right now, you only control the PWM, but that's not inherently identical to speed (think of riding uphill vs downhill). Imagine you could control the PWM to make sure your skateboard rides at a constant speed rather than with a constant torque! You could, again, go the classical, 1960's route of doing that with an analog control loop, and then tuning parameters until things work out, or you could just do it in microcontroller software.