First off, don't lie on the word count. That'll just make you look bad when the agent notices the difference.
The word count issue is always a tough one. Sci-fi/fantasy is one of the genres that can get away with being longer, and it's especially frustrating when we can look at the shelves in the bookstore and see 300,000-word tomes there. But those certainly aren't the norm, and definitely aren't first-time novels. 120,000 is already pushing the edges, to be honest. Some agents might auto-reject at 120,000 and only be interested with shorter things, others might be okay with 120k but nothing higher, and some might figure that 5000 words isn't enough of a difference to be picky about. The problem is that you don't know which agent wants what, and those who might accept the higher end of word counts are going to be in the minority, making your life a lot more difficult.
So, yeah, you're in a bit of a tough spot, but if it's any consolation, the first book I wanted to get published was a whopping 250,000 words, and I know I won't ever get that behemoth under 200,000, despite knowing there are needs for cuts at this point. So it could always be worse.
My advice is actually basically what I'm doing with that aforementioned behemoth. Set it aside for a moment. Don't let yourself touch it for several months, at minimum. In the meantime, occupy yourself with other writing projects. But taking a step away (and the longer break you take, the better), then the easier it is to come in with fresh eyes and see that there might be a couple extraneous things you can still pare down. I believe you when you say you've been working hard at cutting, so I'm not trying to diminish that. And I absolutely believe that you need to tell your story as it needs to be told, so you can't cut to the point of damaging that. But there might still a few things that right now you are just too close in to realize are unnecessary, so taking a step back for a while will allow you to see them. I can vouch from personal experience that taking breaks allows me to see the flaws and how to fix them a lot more clearly.
If, after all of that (or if you've already done that), then you can try querying at 125,000 words. It's not impossible, it's just a lot harder, so you'd better be sure you have a squeaky-clean, tight manuscript and a damn good query. And then still be braced for a lot of rejections. But 125,000 words can happen for a first-time novel. So good luck.