No credit card required
Browse credit cards from a variety of issuers to see if there's a better card for you.
Get you util down then the closure of credit one card wont mean much. Dont need to replace a card with a card. Do some more housekeeping and aviod the HP, hit to your AAoA's and adding a new account. Scores need to rise some more. Just shut it down. And yes time will heal all things.
Call collection company. Confirm that the call is recorded. Have a figure/percentage of balance owed that you will offer. Tell them you would like to offer to settle for % of the balance in exchange for their agreement to report 'paid in full'/or 'settled in full' to all major credit bureaus and deletion of tradeline. (they rep may balk at the initial offer, but if it is appealing and almost immediate, you could get a favorable result) Also, if necessary ask them to place you on hold and check with their supervisor (this worked once for me...probably just luck but..).
After everything is confirmed - and BEFORE you provide payment make sure they agree to send you a letter via email confirming the agreement to report to all bureaus with the delete.
With your existing cards, you may be eligible for CL increase. Sometimes it is just a matter of dialing the 800 number on the back of your card, or going online and requesting the increase. Make sure it is a soft pull. It might be better to call and confirm it is a soft pull.
Good luck.