Eliminate the Game's Abstraction
A RPG is a game where the player takes on the role of a character and makes decisions as if they were the character. In order to make things fair and balanced, the game rules impose limitations, but a character isn't aware of these limitations in mathematical terms, just like your players aren't (usually) aware of the same limitations imposed by real life.
If you take on the role of handling the rules and abstractions yourself and leave the decisions up to the players, they will feel more engaged the the story and the characters and scenarios, instead of being dragged down by the math.
Keep the normal character sheets yourself with your DM gear for reference. Create new character sheets that don't include any math; use plain sentences to describe relative strengths or weaknesses, and state their skills and powers plainly.
Create a more cinematic experience
When the players perform actions, have them describe what they are doing and what they intend to accomplish. If they ask about numbers, tell them not to worry about them. Give them advice about whether they would reasonably expect to succeed, and offer alternative methods more in line with their character's abilities to reach their goals if necessary.
Allow the players to be inventive. One of the things that rote memorization of the rules can cause is a removal for novel and creative solutions to problems. The rules for Skill checks are simple and the rules for Combat are complex, so Combat is remembered more and is used more when it doesn't have to.
I've played with two groups of brand new players that met every other week, and both struggled to learn the rules just as you describe. One group even after 18 months! A session every other week just isn't enough gametime-to-realtime for things to sink in. What I found with that longer-term group was that after I started just doing the math for them they were happier and more engaged with the story that was being told.
There are more than one kind of player, and not every player wants to be a rules-master. Some just want to show up and play, and don't want to be bogged down in the math. This doesn't make them bad players, it just means that if you want to play with them you have to cater to their needs.
One of the problem that I find with players coming to table-top from video games is that they tend to get too rules focused, and stop being creative. You've got the chance to nurture creativity in new players. Even if it means extra math work for you, that creativity will make memorable experiences that will be worth it!
(Using one of WotC's pre-existing characters, here is an abbreviated prototype 'numberless' character sheet.)
Steve is a human fighter. He is 6' 2" and 280 lbs, not counting his armor. He has dark hair, sun-tanned skin and hazel eyes. Formerly a soldier, he has many scars on his arms, chest, and distinctive line on his left cheek. He still holds himself as if he were an officer, and many still serving still address him as 'Lieutenant' when they buy him a drink in the local pub. They often ask for tales of his exploits against the orcs, where he had earned his reputation through skill and dedication, even learning the orcish tongue to give him a tactical edge.
Steve is very strong, and has rarely met someone stronger. He is also tough, and his training make him particularly skilled in completing tasks the require his strength or toughness, especially athletic challenges. Steve is also charismatic, and uses his conviction and strength of character to inspire others but is specifically trained to be intimidating, on or off the battlefield. Steve has a slightly above-average intelligence, and has extensive knowledge of history from officer training school. Steve isn't the nimblest, and struggles performing acts requiring dexterity. Time on the battlefield has given Steve above average perception, though he doesn't have any natural predisposition for or against it.
As an excellent soldier, Steve is trained in all armor types and weapons, but he prefers his old trusty chain mail and longsword. In order to be prepared for the unexpected, he also carries a pike and a handful of javelins into combat, as well as a shield. Between the heavy armor, the shield, and long battlefield experience Steve is tough to hurt in combat, and his strength and skill with a sword make him a force to be reckoned with.
Steve's favored fighting style is a protective one, learned on the front lines where the soldier standing next to you will save your life if you save his. He can use his shield and his quick reactions to help hold off an attack from a nearby ally. Steve's battle-hardened body is used to combat, and can find his second wind when others are losing steam.
Basically, you just describe what they can do. For someone who cares more about their character and the story than the rules and the numbers, this tells a player who their character is and what they are capable of much better than Str: 16 (+3). More importantly, it puts things in perspective, because it's hard to tell just how good a +3 is; yes, every +1 is important, but when everyone in the party has stats in the 15-17 range it's easy to forget that the player characters are exceptional.
A player who doesn't want to learn the rules can use this description to make more creative choices based on who his character is and what the character is good at and capable of, based on what makes sense to the character. A player who wants to learn the rules but struggles with it could use both the descriptive and the mathematical, so that he has a reference point for what the numbers mean.
In my experience, there is one reason why anyone learns anything: the learning has meaning. By attaching meaning to the math the math will be easier to learn.