Interesting to note: every president who was elected without winning the popular vote was defeated for reelection, until Bush. I'd think that he certainly loses reelection without 9/11. I think we'd see Hillary Clinton elected in '04; a non-wartime president is much easier to unseat, and she flirted with a run in OTL anyway.
Fight Club ends with a major bombing right? Maybe we have that, a much more organized and threatening domestic terrorist movement that is able to grow in the early 2000s without the anti-terrorism vigilance and homeland security movement.
I think it would be difficult for Bush to win in 2004, but I wouldn't call him losing a certainty. I will say however, that Congress would probably have gone to the Democrats in 2002 without 9/11. It might not be by as big a margin as 2006, but they'd do much better than the OTL.
Let's look at the previous House elections:
Year: # of Seats (% of popular vote)
--------------------------------------------------
1996: 228 R - 207 D (47.8% R - 48.1% D)
1998: 223 R - 212 D (48.0% R - 47.1% D)
2000: 222 R - 213 D (47.3% R - 47.0% D)
*note* I counted Independent Bernie Sander with the Democrats, and Virgil Goode with the Republicans.
So Democrats gained seats each election, and the popular vote was within 1% each election. Then in 2002 we get:
2002: 229 R - 206 D (49.6% R - 45.0% D)
Republicans increased their share of the popular vote while Democrats decreased, even though Republicans controlled the White House and House at the time. This goes against the norm for midterm elections ever since 1934. After 1934, the party in control of the Presidency always got a smaller share of the House popular vote in the midterm compared to their performance in the previous Presidential election year until 2002. 9/11 had to have been the event that caused the change in this pattern, and as we've gotten further away from 9/11 the pattern has returned.
So with a 4% swing Democrats would have won the House popular vote 49.0% D - 45.6% R. That holds to the pattern, and I think that would be the worst Democrats would have done in a no 9/11 world. There is also the possibility that the big issue driving Democratic turnout would be the belief that the 2000 election was "stolen" from them, which could mean they are more energized and could win the election by an even bigger margin. So with a 4% swing from OTL, Democrats probably just barely take the House 219 D - 216 R. With a 5% swing from OTL, they should get 224 D - 211 R.
Democrats should make gains in the Senate elections that year as well. No 9/11 might even butterfly away the death of Paul Wellstone, but even if it doesn't Mondale only lost by 2.2%, so a 4-5% swing compared to the OTL would give him the win. Jean Carnahan probably holds on in Missouri, and Max Cleland has a chance to hold on in Georgia. Democrats have a good shot to pick up seats in Colorado, New Hampshire, and North Carolina. Worst possible results for Democrats would be 53 D - 47 R, best possible results 55 D - 45 R. I counted Independent Jim Jeffords with the Democrats for those numbers.
So without 9/11, the Democrats should win control of Congress in 2002. This will change how President Bush governs for the remainder of his term(s).