I don't see enough information about the details of these files, but it appears that there is a 1-1 relationship in them and this solution is based on that assumption. If this is not true, then this solution will not work.
This solution is to send each of your input files through separate sort processes that will assign a sequential number to each record and adds that value to the end of the file. I assume that your file is 29 bytes long, so this process will add a sequence number that is 7 bytes long to the end of the file (columns 29-36). Then a sort join process is done using both your original key in columns 1-3 and the sequence number in columns 29-36 as join key values. This output should give you what you have asked for.
//SORT1 EXEC PGM=SYNCSORT
//SORTIN DD *
123 AAAAAAAA 2010-05-06 FFFFF
123 AAAAAAAA 2010-04-06 GGGGG
234 CCCCCCCC 2010-07-09 KKKKK
456 DDDDDDDD 2010-09-05 PPPPP
456 DDDDDDDD 2010-06-06 RRRRR
/*
//SORTOUT DD DSN=SORT1.TEMPFILE,
// DCB=(RECFM=FB,LRECL=36,BLKSIZE=0),
// DISP=(,CATLG,DELETE)
//SYSOUT DD SYSOUT=*
//SYSIN DD *
INREC FIELDS=(1,29,SEQNUM,7,ZD)
SORT FIELDS=COPY
/*
//*
//SORT2 EXEC PGM=SYNCSORT
//SORTIN DD *
123 1998-09-08
123 1997-05-06
234 1996-07-08
456 1995-09-02
456 1994-01-01
/*
//SORTOUT DD DSN=SORT2.TEMPFILE,
// DCB=(RECFM=FB,LRECL=36,BLKSIZE=0),
// DISP=(,CATLG,DELETE)
//SYSOUT DD SYSOUT=*
//SYSIN DD *
INREC FIELDS=(1,29,SEQNUM,7,ZD)
SORT FIELDS=COPY
/*
//*
//STEP0030 EXEC PGM=SYNCSORT
//SORTJNF1 DD DSN=SORT1.TEMPFILE,
// DISP=SHR
//SORTJNF2 DD DSN=SORT2.TEMPFILE,
// DISP=SHR
//SORTOUT DD DSN=SORT3.OUTFILE,
// DCB=(RECFM=FB,LRECL=29,BLKSIZE=0),
// DISP=(,CATLG,DELETE)
//SYSOUT DD SYSOUT=*
//SYSIN DD *
JOINKEYS FILE=F1,
FIELDS=(001,003,A,
030,007,A) SEQUENCE NUMBER
JOINKEYS FILE=F2,
FIELDS=(001,003,A,
030,007,A) SEQUENCE NUMBER
REFORMAT FIELDS=(F1:01,13,F2:05,10,F1:24,6)
SORT FIELDS=COPY
/*
//*
//