Here is a way using hidden columns that does not require VBA. This does not sort the final column, however.

After entering these formulas, you can hide the three columns in the middle by right-clicking their headings and selecting Hide:

And that will leave you with this:

The formulas in the four columns after Col1 and Col2 will have to be copied down to at least twice the maximum length of Col1 and Col2. I suggest picking an arbitrary large number that you feel certain your Col1 and Col2 number of rows will never exceed and then just forgetting it.
This assumes that your Col1 and Col2 are in columns A and B and that the header row is included and the header row is in row 1. You'll have to modify these slightly if no header row is included.
The Combined column's formula:
=OFFSET($A$2, FLOOR((ROW() - ROW($2:$2)) / 2, 1), MOD(ROW() - ROW($2:$2), 2))
The Filtered column's formula:
=IF(C2 = 0, "", IF(ISERROR(MATCH(C2, C$1:C1, 0)), ROW(), ""))
The Sorted column's formula:
=SMALL(D:D, ROW() - ROW($1:$1))
The Col3 column's formula:
=IFERROR(INDEX(C:C, E2), "")
The way this works is to first combine Col1 and Col2 starting at the first row and proceeding downward (Cell A2, Cell B2, Cell A3, Cell B3, etc.). It does this by using a combination of the OFFSET function combined with the FLOOR, MOD, and ROW functions.
Then we filter out duplicates by testing whether the value exists in the current row through all previous rows. We use the MATCH function for this in combination with some clever use of absolute and relative references. The row number is returned instead of the value so that it can be used in the next two columns.
Then we bring all the listed row numbers to the top by a combination of the SMALL and ROW functions.
And finally, we just need to return the INDEX of the Combined column corresponding to the row of the Sorted column.