Oh my goodness.... you and fiance need to buckle down HARD and you might do just fine, but if either one of you decides that you're not willing to give up a few luxuries, you won't make much progress.
You have hair on fire debt and are not going dig out of this without sticking to a serious no-frills budget, and/or bringing in more money. You admit you were crazy about racking up charges through your younger days, so thing to realize is that you're both going to be paying for it now by denying yourself all those luxury things you've taken for granted as necessary (like lunches at work).
Every dollar you spend now on non-essentials is a dollar that digs that debt hole deeper. You really, really need to have a complete 180 on how you view spending and debt because until you get this straight, it's too easy for you to keep trickling away $5 here, $10 there and never really get out of trouble.
Fiance needs to get or keep part time job working as many hours as they can when they are not in class, doing classwork or sleeping. It's lovely that they got grants to go back to school, but you have hair on fire debt and expecting you to shoulder the lion's share of living expenses and debts accumulated while they go to school is not fair or a great way to start out life together. You are a team, so both of you need to be working together hard as possible to get this ship back on course.
You need to consider a second job if your current one doesn't allow overtime. Anything that is close to home or your 1st job, and can provide you with extra money to throw at the debt.
Track every penny of expenses ASAP. Get Mint, YNAB whatever but you are missing way too much spending that everyone forgets about (cleaning supplies? toilet paper? soap, haircuts, clothes? Do you drink? Entertainment expenses?), and without knowing where your money is going you won't ever be able to properly stop up the bleeding and funnel the money to where it needs to go.
Cut everything that is not necessary for basic living:
NO sling tv.
No gym (check out bodyweight routines, yoga and walk/jog trails for free exercise)
No eating out at all
No lunches at work
No presents
No clothes shopping
No fancy toiletries or name brand, single serve stuff
NOTHING THAT ISN'T VITAL FOR LIVING
Insurance on jewelry is weird - how could you afford a ring that is so expensive that it requires insurance? Who paid for it? Can you return it and get a simple silver band or really ANYTHING? I am flabbergasted that you would buy (or your broke fiance) a ring that cost more than a few hundred... this is madness. You can get a "nice" ring for an anniversary when you have actual money and can afford it.
No more pets. I would not tell you to get rid of your animals, but do not spend a single penny more than necessary, and do not adopt any more until you're out of debt. Right now, assess the costs involved on their food/litter/etc., and see about finding cheaper alternatives ASAP. The big thing that people seem to forget: pets are a luxury. What happens if you have an emergency vet bill? You're screwed, because you will either have to go into even deeper debt or make a very terrible decision based solely on the fact that you can't afford their upkeep. Take as good a care of your existing pets as you can, but cut costs - Aldi for instance sells large bags of dry cat food, canned food, scoopable litter and treats even. Buying larger containers when possible will save more usually (assess the cost vs weight of product - this is important with groceries as well to assess whether the price is a good deal).
Lunch at work? No more lunches out at all and that includes at work. You say it's only $6 or even $3... that's still VERY high. Sure, not as high as going to like Panera or Chipoltle or something, but if you cook at home, pack your lunch, you can get it under $1 or closer to 50¢/lunch easily. You are (say it with me) in HAIR ON FIRE DEBT, so saving $100/week is $400 a month, $1,200 a year. This is HUGE!
And groceries... $500 a month on groceries for 2 people. This is INSANE. It should be closer to $250. Learn to cook simple meals. Batch cook, and freeze into portions so you have a week's worth of lunch and dinner ready to go. Shop discount grocery stores and only sales - no buying fancy stuff or convience packages. Bulk rice and beans with a bit of spice/oil could be the basis for a great meal. Then add in a bit of cheap veggies for variety. Frozen veggies are cheap, but can buy fresh veggies that are on sale if it's a great deal, but NO NON-SALE ITEMS EVER. Check out the clearance sections too - dented cans still have good food in them, meats due to go out in the next day or so for half price or better are still good and can be frozen if you can't eat it all within a few days of purchase.
Organics are a luxury. Meat as the main part of a meal is a luxury. Prepared foods are luxury. Boxed or bagged or fancy meal plans are luxury. None of this should be on your shopping list until you are out of debt and have a healthy emergency fund built up. Check out budgetbytes.com for great, easy recipes for pennies.
Definitely get out of that phone contract ASAP. I don't know what is available where you live, but many MVMOs now offer payback for breaking a contract. Get the cheapest phone you can find, and the cheapest phone plan you can find. I can't even imagine buying a phone for over $500, and I'm assuming your fiance is also on the same plan with an expensive phone. You should be able to get that bill down below $50 after phones (which should be under $100 for both). No one needs unlimited data, text and voice. Treat your phones as emergency contact only and not as entertainment - texts and short calls only and no data unless it's an emergency. You can't afford entertainment like this.
Cheapest beater car you can find that is mechanically sound as soon as you can get rid of the stupid lease. NEVER GET A LEASE AGAIN. And get basic required insurance coverage and drop the full as soon as the lease is gone.
As far as the debt - every penny you can scrounge should go towards paying down the CC debt first. I would also start paying back the relatives (track this carefully) at $10 each/month just to show you're serious about paying them back. But the bulk of the money you save should go towards the high interest debts. Pay the minimums on the other debts until the high one is gone, and then switch to the next highest (the sofi?) with everything you have (maybe increasing the friend/relative paybacks to $25/month after the highest one is gone).
You can turn this around in a relatively short period of time - honestly if you and the fiance worked hard at cutting costs and cooking at home - you likely could be debt free in 2-3 years even with him working part time. But it would require you both to really work at it and sacrifice a bit so hopefully you're both strong and determined enough to go forward on this. Good luck!!