Something about this situation seems off to me. Are you certain that you and your PI have been on the same page about this manuscript? When you were ready to submit the last time, was the manuscript 100% ready to go out the door (formatting, references, title page, abstract, etc.)? I am trying to think of why a faculty member would have lied about this, and one thing that occurs to me is that it could have been a way to back out of a paper that he or she was not actually prepared to send out for some reason. That would be a cowardly thing to do but the thought comes to mind.
You're in a tricky situation but it's worth being assertive and trying to move things forward. Take ownership of the situation and try to get your PI to agree to some next steps. Make it easy for him or her to just say "OK." I would sidestep the matter of the fictional past journal submission and just look ahead.
I agree you should try to submit the paper yourself. Some online submissions systems are persnickety, which can be annoying, but it's not really difficult. Journal web sites have instructions (which few seem to read) that give you most of the information you will need. You can email the managing editor if you get stuck/lost. You can name your PI as the "corresponding author" even if you are the one to submit it. Ask to be cc'd on the journal correspondence as you'd like to learn from the process.
I like the tactic of saying "Unless there are major revisions necessary that I am unaware of, I would like to submit to Journal X by MM/DD," giving other authors a couple of weeks to write back with any further revisions. Just pushy enough to be effective!