Bipolar stepper motor (Alfa Romeo 156 speedo) w/ L293D

1. the ULN2803A has already lots of protection diodes.. safe enough?

Yes.

2. the Mitsumi M55SP-1N datasheet says 259mA/phase*4=1,1Amp..correct?

Yes (close enough). The resistance of each phase is 50Ω +-7%, so at 12V it should draw approximately 12/50 = 240mA per phase (actually it should be even less than this, due to voltage drop in the Darlington transistors).

3. powersupply of 1.25 Ampere....enough right?

Yes.

A strange thing happend .. @5v with high speed stepping the ULN2803A got hot. 50-60 deg C. normal?

Getting hot at high speed is to be expected. Each time a coil is turned off the flyback diode passes a pulse of current as the magnetic field in the coil dissipates. At high speed the diodes pass as much current when the coils are turned off as the transistors do when they are turned on, which increases total power loss. The transistors also have a switching loss which becomes more significant as stepping speed increases.

50-60° case temperature is OK. The ULN2803 is not very efficient. At 240mA each Darlington transistor drops about 1.1V, which equates to 1.1W of total power loss when all 4 phases are turned on. Maximum allowed junction temperature is 125°C. Junction to Ambient thermal resistance is 73°C/Watt (D package), so at room temperature (20°C) and 1.1W the junction temperature should be ~100°C.

uln2803 handles 500mA per channel and a max of 2,5A ....

Those are absolute maximum stress ratings, not recommended for normal operation. For safety and reliability you should not exceed half those values.

it appears what you need here is a 2 cell lithium battery. Li-po(nominal 7.4) or li-ion(nominal varies, but more than lipo) would probably both work. Worthy of note though, is that adding a lithium battery to a project safely adds quite a bit of complication. Unlike other battery chemistry, these do not drop to 0V at discharge, but are considered "discharged" when there is still over 3V at the terminals. Discharging the battery farther will cause damage to the battery and most chargers will refuse to recharge it. That being said, as long as this isn't an autonomous project, any method of checking the voltage will work. The vast majority of modern RC cars use 2 cell lipos, so they can be had for resonably cheap. http://www.hobbyking.com/hobbyking/store/__6540__ZIPPY_Flightmax_2200mAh_2S1P_20C.html You also need specialized charging circuitry as well.

If all of this is too complicated, you should be fine with 6 AA batteries. You can buy whichever rechargeable brand you like. That will give you approximately 4X runtime of your current setup and requires no voltage monitoring.

With regards to power supplied to the stepper: Most steppers don't care much about the voltage supplied to the terminals, as the insulation is rated for much higher voltage than you could apply with simple batteries. What they do care about is amperage. More specifically heat If the motor is getting too hot to old onto chances are you are on your way to burning it out. Steppers are 2 phase brushless DC motors, and the permanent magnets inside will become permanently not-magnets if they get too hot. Looking at the easydriver website, it appears there is a current limit setting on the driver. Set that somewhere under the maximum rating for that motor and you're good to go regardless of input voltage.
Cheers.