これって不自然な文章ですか？

最初の「I saw him」はその瞬間のことで、後の「push my bicycle to the library」はその瞬間の前から始まっていてその瞬間も続いていたものですよね。
この場合、文章自体が過去のことであっても、続いていた事は現在進行形にする必要があります。
つまり、
I saw him when I was pushing my bicycle to the library yesterday.
が正しい文となります。