Your question breaks down into distinct subquestions and assumptions, we need to call out each of them separately, especially because you have the importance wrong:
- How important is being first named author [as long as you're second, obviously], in your field. You claimed "being first author means everything for me in my application"
- Is fighting this fight worth it? Is it strategically worth picking this one or letting it go? 2b) Also: is it important going forward to preserve your relationship with professor (especially if it sounds like you'll stay in the same dept?)
- How do you actually prove you originated the work/ideas? (This is pretty self-evident and is the least important question)
Answers from experience (almost all of us know people who've been in this situation):
You seem to be making a huge wrong assumption here, seems like you extrapolated the application's artificial format to believe in general you will not get any credit unless you're first-named. Generally everyone knows the deal with academia and tenure-track, it's an imperfect little world, people will understand he is under pressure from his own tenure-track metrics. Yes it's somewhat bad ethics, but this is utterly different to omitting your name entirely, stealing your idea for a startup or patent, esp. when rejecting the associated thesis, stealing your funding and redirecting it to other purposes etc. Outside in the real world noone gives a **** if you were first named author; at interviews or in applications you will be given adequate chance to demonstrate whether you were/were not the prime mover; in fact people may respect the team-member vibe if you diplomatically say "we" and "our idea" while making it blatantly obvious you did the work and wrote the professor's ticket.
To quote Def Leppard's fine song, "Let It Go..." You have to answer this question: on a scale of 1-10, how was prof's behavior overall, and factor in "he told me he will compensate in my recommendation". Sounds like an 8/10 to me. Believe me, there are scumbags out there, and it ain't him.
Pretty self-evident, and irrelevant. Notebooks, notes, SCM checkins, emails, drafts. If in future you get a really clever idea [while in academia], send a dated email to yourself (/burn a CD and certified-mail it yourself, unopened). Read also about the concept Reduction to practice in US patent law, for the future when you're working for a company.