http://www.microsoft.com/en-us/download/details.aspx?id=30679
Ok just a moment. I just got it to work. allow me to enumerate the steps I took.
Go to the above link. Download both the x64 and the x86 versions of the redistributable.
install both. Pick repair if given the option.
The MSVCP110.dll should appear and the game should work.
I am not sure if the thing just doesn't exist in the ones sent by EA (Which would be hurarious) or what.
Other things I have done that might have helped:
Installed all updates to windows, including .net framework 4.5.1
created a new, separate account on windows with full administrator privileges and used that account. (Important! should be separate, even if your regular account is an admin)
Ran the file located at C:\Program Files (x86)\Origin Games\Battlefield 4\__Installer\directx\redist\DXSETUP.exe.
Updated my graphics driver.
I think it was the new redistributables that did the trick though. Install both of them.