I have seen some rough stuff. That means that part of this letter is written essentially speaking to those other people that I knew. The things that I'm going to say are good for them. I hope you are not as lost as they were. It will make the suggestions even more effective.
If you happen to be less damaged/lost then some of the content of the answer might sound aggressive. It will sound like I am saying "quit" when in fact I am saying "go". Please hear the encouragement and specific actions from this answer. Only in the worst cases am I saying "walk away". It has to be said sometimes - there is a good reason why every government in the world has the right to take kids from bad parents.
I am the oldest of six kids, from a family-proliferating culture. My father is a perfect wreck - likely the only good thing he did in his life was procreate us kids, and his job would have been done with less damage and evil in the world if he died immediately after we were all conceived. He is a monster. When my mother ran from him, she never stopped running. She is still running today. We moved every 3 months for years and years. I grew up on welfare. Not one of my family members made it to 16 unmolested. Most of our friends were also on welfare, so very poor. Many were also abused. Bottom line: I know what deadbeat looks like on the receiving end, and have seen what does and does not work, so I can speak to it with a little authority.
You may not like the tone or substance of my answer. I'm writing what actually works. You don't have to like it. I recommend that you try for a whole month (literally 0.1% of your life) doing it all. Keep a journal/log for each day. At the end of 30 days take stock and see if you have made progress toward the goal. Empirically validate the results.
When my sister was looking at divorce, and her 5 year old daughter had no daddy - I told her "You could give her the best in the world, and they would be a B+ but if you took her deadbeat dad and he tried - even though the world saw a C, he would an A+ to her." Ineloquent, right? Children are engineered to respond to their biological parents. There is some conversation about initial imprinting on the perinatal child, like geese, but after that the mechanisms are set for that developmental stage. Still ineloquent. If you actually work at it and stick to it then you can do a lot of good in your daughter's life.
This is the part that sounds like "no", but is really "be real":
About 15 years ago, on Christmas eve, I met a lady literally inside the dumpster of my apartment complex. She was weeping and desperate. She needed something for Christmas for her kids (the state had taken them) and she was digging through trash looking for .. anything. True story. After much midstory - she got custody of her son but not her daughter. But then she fell back into the addiction, and introduced him to it. She got a new boyfriend - big, muscular, and very capable of violence. He chased off her husband, and that marriage was over. The tweaker son started "converting" his friends until they had a whole club of high-school age tweekers living in that apartment, painted the windows, cooking meth - it was bad.
She should have been left in the dumpster - because while her ruined life would be ruined, that of her son, of her husband, and of all those kids her sons age - they would not have been destroyed as well. There would have been a lot less huge collateral damage. That sad woman and all that waste ... long gone. Nothing to show for amazing grace and another chance that nobody got, that she got, that she not only wasted but utterly burned to the ground.
Don't be her. Don't be like her. Not even a little. If you are going to end up doing something monstrous to your daughter - your wife left for a reason - then just walk away. Let it go. Give her the least gift, the Darwin award gift - of blessing her life the most by not being in it. If you are owned by meth, or oxycodone, or heroin - just walk away.
If I tell you how to make it right, and you can make it right, and then you wreck your daughters life - the universe is going to be very very angry at you for it. You are required to live up to the truth that is in you.
Bottom line: don't "come to play". Come to win. Come to "die with your boots on".
How to measure deadbeat-ness (or lack thereof):
I teach my daughters than any worthless guy can talk and act like a perfect prince charming for ~3 months. He will say only what you want to hear and do only what you think a perfect charming does for about that long. Narcissists have less endurance. This is the edge of the envelope that willpower and hormones give them. After that window they start having failures - they start becoming obvious. Some start playing dual-games. Some quit. Some "man up" or "human up" or grow a soul.
The way to not get used/fooled/broken is 1) words, 2) actions, 3) over time (much greater than 3 months). Remember his words, and actions, and how they line up, over time. Life is the long run, not the sprint. Meaning and significance only show up if you are in life for the long run.
My (genius) wife says there is a passage of the bible that gives all these things that make up a true love and if a boy can't meet them all then he isn't actually loving. It starts out "Love is patient, love is kind, ...". If you can't put his name in there where "Love" is, and think through his words and actions over time and it be true then he isn't actually loving. If she can't say "Cameron is patient, Cameron is kind" and think over his words and actions and agree that he is in fact patient and kind - then Cameron really isn't actually loving. He can emit the sound "love" but in truth it isn't what he is or what he is doing.
Here is the whole text:
(1 Corinthians 13:4-8) Love is patient, love is kind and is not jealous; love does not boast and is not arrogant, it is not rude; it does not seek selfishly, is not easily angered, does not keep a record of wrongs, does not rejoice in unrighteousness, but rejoices with the truth; bears all things, believes all things, hopes all things, endures all things.
If you are actually growing in those criteria, then you are loving. Then you are not being a deadbeat, and you are moving away from a deadbeat.
Execution: Paying your debts.
Your starting place is earning credibility with mom. You owe the mother, pay back your debts. She is the gate-keeper. Don't start big, or ostentatious. Paying back $20 a month for 100 months is better than promising to pay back 200 a month, and only doing it once. Read the book "how to live on 24 hours a day" once a day - it will give you some wisdom about how to think through keeping disciplined programs in your life so you can actually do the $20 a day. Seriously. Buy the book, in paper and read it. Re-read at least one chapter every day. Seriously.
Execution: Speaking the truth.
I taught my niece this - when you lie, it lives in front of you. It eats away at who you are, and at things around you. It owns a tiny piece of your soul, and the more you lie (the bible calls the devil 'the father of lies') the more it owns. The way to stop all the power of the lie is to speak the truth. You need to speak the truth in front of every lie and every harm you have given. Lies, like secrets, only have power when the truth is not present.
You should work on a letter that tells your wife the truth exhaustively. Write down every single thing you did bad and what you should have done. Not a con. It will hurt you to write it, and you will be scared to give it to her or you aren't doing it right. Write down every last little thing you did wrong. Say what you did wrong, and what you should have done. Don't justify at all. Just say what the truth is. If you lied, then say what the lie was, and what the truth is.
The letter is not about you. It is about what you did versus what you should have done. It is not how you felt. It is not what you wish. Make it clean - and not filled with baggage. Make it so that true substance is as easy for her to process as possible. The goal isn't emotional catharsis for you, it is truth and actual healing for her.
Don't present this as taking from her. When you give her the letter say that is a way of letting go. Let her know what it is - a written list of everything. Let her know that if she wants to burn it without reading it, she may. Tell her you are sorry for what you did wrong to her, and she deserved to not have that happen. She deserved somebody better than you.
Ask her to read through it, and tell you if there is anything you missed. If you owe her truth, and you owe her saying that what you did was wrong and she deserved better - then give her the chance to tell you where it is, and do something about it.
She might let your daughter read it. She might use it as a weapon against you through your daughter. You can say "I made enough hurt for her so maybe not adding to it with this is a good thing". You can say "whats-his-name is a good dad, so maybe he is the dad she should know".
Make a photocopy of the letter and keep it for yourself. Read it at least once a month - and see if you are more or less like that screw-up. If you know who not to be you can be surprised how you are less and less like them over time. This can keep you from the darkness, and also show you the light that you are becoming. It is not a bad thing.
Some day your daughter is going to search for you, try to find you. If the family is perfect, she will still want to meet you and know who you are. Given that your ex was drawn to you - I suspect that your daughter will have more than an equal share of sad. She might not get a train wreck, but you are proof that your ex has a little damage. This, allowed to go its own way over time, will either get resolved with qualified and excellent counseling, or it will make your daughter pursue you sooner.
There is a book called "Letters from Dad". Read it. Execute to it. When you and your adult daughter meet up in a restaurant, you can give her an amazing gift that transforms her identity for the better, transforms her life for the better, and plugs a couple of gaping holes in her heart, and maybe her soul. This is an avenue of approach where if you always engage, you always win. It is the total opposite of Loki in Avengers (link). In life those sorts of "always win" approaches are rare, so engage here.
The instructions that I am giving sounds like the opposite of what you want. Don't trust your current intuition. The goal is the well-being of the child. The approach is about the kind of truth that stages for actual credibility. It is win-win-win.
Be faithful in your paying back for the wounds. If you can make mileage there, it will be worth it. In your character. In the long run. In the lives around you. In your daughters future.
Execution: how to change the person you are
Act from the person of a man of integrity for long enough, and you will transform yourself into it. "Fake it till you make it" actually works in just one place - oh, but it is a good place - it works in personhood. If you act and speak from the character of the person you should be, then over time you will become more and more like that guy. Eventually you will be him. The real challenge - the magic - is in the vision. If you act from a trite pretentious inbreed who is pretending to act nice - you become that. You have to think through well and deep what actual excellence is.
I find that "ensemble methods are robust". It is nerd-speak, but it says "get a statistically acceptable sample of insight". In statistics, 1 is a poor sample. 5 is pretty weak, and 30 is starting to get good. Find 30 really good examples of excellent character, and try and act from the "vote of the field". In all of your dealing, from homework, to housework, to car care, to bill paying, to how you treat your coworkers, your boss, and your customers - find what the most excellent way is and act only from that. It will transform you. If you are tired say "how do they deal with tired". Read up, actually study. Personally I would recommend a "great books" study, but that is an answer for when you are farther down the road to ... life, health, improvement.
Execution: Protect the kids' best interest.
Part of credibility to mom, and truly giving good value to the kiddo - guard mom's current marriage - start by respecting her man as her man and respecting her as never being yours again. Come to terms with it. Never cross that line. There are not many things that will wreck a daughter's life like being a child of a single parent - statistics say what politicians can't. Single parenthood is bad for all the outcomes. You might (remotely) get lucky and be an outlier, but tens of millions of historic cases say - the most likely outcome is not so good. If you want that little girl to have a future then she needs a mommy and a daddy who are in her life, who love each other and her, who are a team working to give her the chance to be a successful person.
Execution: keep your eye on the prize.
What we stare into - we are changed into its image. If we stare into the darkness then we are changed into the image of the darkness. If we stare into the light then we are changed into the image of the light. If we stare into ourselves ... it is like a literal mental analog of how inbreeding destroyed the ancient Egyptian monarchy. They could only marry royalty, and so they inbred. Inbreeding means that all these (mostly broken) recessive traits get amplified and expressed. After a few generations of that the Royals then had a host of genetic diseases and frailties to cover up. They had a bad mortality rate.
If we stare into ourselves for too long, it is like the millionth photocopy of a photocopy - it degrades. Eventually it is unreadable.
Stop looking at yourself. You live in a society of pathological narcissism and it is poisonous. Get fresh air, sunshine, and exercise daily. Seriously - get a 24 hour fitness membership and literally put one hour on the elliptical 6 days of every week. Go give some time to the poor every week - go serve in a soup kitchen and let those folks talk to you. Look at their bad choices. Look at their habits of decision and execution. Learn from folks who know how to screw it up, and regret, so you don't have to.
The exercise will make how you feel different. The bilateral stimulation of your brain will help you process through your broken-ness better, both thinking through it and emotionally processing it. A healthier, fit, you is the kind of image your daughter needs to have for father because when she is older she will unconsciously look for a man with many of your characteristics. This is the tape-recorder thing.
The serving the poor (think Feed my Starving children) is how you make sure that you aren't just doing this for a day or two. It is a practice that helps you stay afloat, and helps you stick through the long run. In jogger nomenclature this "gum and headphones". It is something easier than the hard thing that makes you able to do the hard thing 10x longer than you would. This is a place of immense wisdom about what to do for hurts. I'm sure nobody has told you this but there are 200 bad answers for every 1 really good one. They can help you find the 200 ways not to do it without having to learn the hard way. Let their wounds buy you your healing. Talk to them. Listen to them. Get the free good wisdom they have.
Don't break the 4 year old's heart.
I believe in God and with my own eyes have seen the power of prayer. If you believe in God then you should pray for the health, well-being, and life of both your ex and your child. I find that specific requests help, both in scope and results. Instead of saying "God do good" you can say "my ex needs to get past hurdle x this week, please help her to do a, b, and c to get through it". Example: my ex (use her first name) is trying to make the best decision for her and my daughter (user her name) life, so please give her the direction she needs, help her to recognize it for what it is, please make the alternatives that are less good harder, and help her get through where you know would be best for her.
Example: my daughter is going to daycare. The kids there are often poorly monitored and half-feral to each other. God keep her from being a target by the others. Keep her from learning to be feral like that. Help her to get through her days without being bitten/hit/kicked/robbed/bullied. Build in her the character that while keeping her from being a victim also keeps her from being the aggressor.
When I literally got rid of my television, I discovered that I had another 40 productive hours per week. You should consider staying away from TV or computer screens for a week, and measuring the time you have to be productive. I also discovered that I was dependent on the events of some shows for my sense of emotional well-being. It was an unhealthy object in my life and my mind and self was much better for having been rid of the device.