Just have allied races start at level 20 in their level 20 starting area, with DK skills set so they're like the normal classes in terms of talents.
Figure out what skills for allied race DKs need to be added at level on up. All will be good then.
I would love a VElf Death Knight!