I think (and I may be going out on a limb here) that ALL projects should have a bit of classic waterfall: The initial analysis and specification phase is essential. You must know what you are doing, and you must have it in writing. Getting the requirements in writing is difficult and time consuming, and easy to do badly. That's why so many skip it - any excuse will do: "Oh we do agile so we don't need to do that." Once upon a time, before agile, it was "oh I'm really clever and know how to solve this, so we don't need to do that." The words have changed a bit but the song is essentially the same.
This is of course all bull: You have to know what you are to do - and a specification is the means by which developer and client can communicate what is intended.
Once you know what you have to do - sketch out an architecture. This is the "get the big picture right" part. There is no magic solution here, no one right way, and no methodology that will help you. Architectures are the SYNTHESIS of a solution, and they come from partly inspired genius, and partly hard-won knowledge.
At each of these steps there will be iteration: you find things wrong or missing, and go fix 'em. That's debugging. It's just done before any code got written.
Some see these steps as boring, or not needed. In fact, these two steps are the most important of all in solving any problem - get these wrong and everything that follows will be wrong. These steps are like the foundations of a building: Get them wrong and you have a Leaning Tower of Pisa.
Once you have the WHAT (that's your spec) and the HOW (that's the architecture - which is a high-level design) then you have tasks. Usually lots of them.
Bust the tasks up however you want, allocate them however you want. Use whatever methodology-of-the-week that you like, or that works for you. And get those tasks done, knowing where you are heading and what you need to accomplish.
Along the way there will be false trails, mistakes, problems found with the spec and the architecture. This prompts things like: "Well all that planning was a waste of time then." Which is also bull. It just meant you have LESS foul-ups to deal with later. As you find problems with the high-level early days stuff, FIX THEM.
(And on a side issue here: There is a big temptation I've seen over and over to try to meet a spec which is expensive, difficult, or even impossible. The correct response is to ask: "Is my implementation broken, or is the spec broken?" Because if an issue can be sorted out quickly and cheaply by changing the spec, then that is what you should do. Sometimes this works with a client, sometimes it does not. But you won't know if you don't ask.)
Finally - you must test. You can use TDD or anything else you like but this is no guarantee that at the end, you did what you said you would do. It helps, but it does not guarantee. So you need to do final test. Thats why things like Verification and Validation are still big items in most approaches to project management - be that development of software or making bulldozers.
Summary: You need all the up-front boring stuff. Use things like Agile as a means of delivery, but you can't eliminate old-fashioned thinking, specifying, and architectural design.
[Would you seriously expect to build a 25-story building by putting 1000 laborers on site and telling them to form teams to do a few jobs? Without plans. Without structural calculations. Without a design or vision of how the building should look. And with only knowing that it is a hotel. No - didn't think so.]
I don't think you'll really get anywhere without reworking the way things are done right now.
One example is that during development we only focus on new features
and ignore existing bugs and even introduce new bugs.
I am fairly certain that this is a grave mistake. Try to explain that bug fixing becomes more difficult and more expensive the longer it is postponed. I don't think there is any excuse for postponing bug fixes for so long.
All agile methods I know emphasize that the software should be technically ready to ship at the end of each cycle/iteration (or even continuously). That means any bug that you wouldn't want to ship must be fixed before any new features is started.
Try to work with people, and explain your concerns.
Finally, if you cannot get any kind of agreement on such basics, it may be best to move on.
Edit
Based on your amended question: I agree that bug fixing should be handled just like new features. I'd normally have single tasks for "small" bugs (up to a few hours) and stories with subtasks for "big" bugs (multiple days, possible to split into tasks). If your colleagues do not agree, point out that the advantages of agile methods apply to bug fixing just like to new features.
As to wheter to use an agile tracking tool or a bug database: Ideally, the two are integrated. If they are not, then yes, you'll have to track work in both. It's annoying, but I've done it myself, and didn't find it a big problem. You track bugs as usual, and just copy&paste the bug id into the title of a task/story when you schedule a bug to be worked on. The task is just a link to the bugtracker (eays if both are web-based), and all discussion is in the bug db. If you link consistenly, you could probably even run reports across both systems.
Finally, it you believe you cannot change the way development is organized, you'll have to work within these constraints. Things like introducing some agile methods into the bug fixing phase will probably help.
Still, I am convinced that splitting development into a "feature phase" and a "bugfixing phase" is a grave, possibly fatal mistake. It may not be so serious for your company (every situation is different), but if it is, and if your organization is unable to change this, then your organization may be so dysfunctional that you'd be better off elsewhere. But that is your call to make... good luck!
Edit 2
Finally, if company policies dictate "features first, bug fixing later", maybe you can sidestep them, e.g. by redefining bug fixes as new features (the difference is often a matter of opinion anyway). To some extent, you can try to introduce new ideas "from below" that way. You know, "if you can't beat them, join them".
Best Answer
Check out https://groups.google.com/forum/#!forum/solo-scrum
and https://stackoverflow.com/questions/829497/agile-methods-specifically-taylored-to-working-solo
Update:
The first link is to the Solo Scrum Google Group. The most obvious benefit talked about here is using time-boxed sprints to manage scope and determine project velocity--both very good things.
The second link is to a previous discussion on Stackoverflow, which might indicate this is a duplicate question, but I thought it would be more useful to link to it. It in turn links to http://c2.com/xp/ExtremeProgrammingForOne.html which has a lot of links and info about doing XP solo (sans pair programming).