first, I would pull the carpet currently in there(try to keep in 1 piece) go to home depot, or such, and by some outdoor/vehical carpet. It will run you around $50 or so, then use the old carpet as a pattern, but cut the new carpet a 3 inches or so larger than old carpet. install then trim excess, You would not believe how nice it looks, ive done to my 89 pathy.
I would do all you said, but also the bad gas milage can be cause, by 2 things.
1)tired motor, solution rebuild. If you have the means, and patience i would rebuild the one in there, or pull one from a scrapyard(300.00 in my city) then rebuild, you will be surprised at the power and economy you get back
2)part or all of your emisions system is bad, egr, o2 etc. this can be tricky, I would suggest picking up the chiltons manual and do ever test in the book lol.