How do I re-wire this outlet (switched top, always-on lower)?
This is a lot more straightforward than it looks.  


All the blacks go together, and also to the hot side of one socket. 
All the whites go together, and also to the neutral side of both sockets. 
All the reds go together, and also to the hot side of one socket.  


You need to break off the tab on the hot side of your new receptacle.  

How do we know this?  First, black is the first color people use for always-hot.  And they're all nutted together with a pigtail. So that is almost certainly the genuine always-hot.  Can't tell you where it's coming from.   

Since you have a WeMo light switch, those are neutral, so the white wire on the switch loop must actually be neutral.  Therefore the switched-hot is red.    Since other receptacles are also switched, that also accounts for the other red wire.   Now all the red wires are accounted for.  

The supply must deliver neutral, and the switch and downstream outlet also need neutral.  That accounts for all the white wires.  

By the way, the neutral are hot because they have  loads on them.  Since you disconnected its neutral and it is still connected to "hot", the entire guts of the Wemo are now floating at 120V, including its neutral terminal and the wire attached to it.  The same is true for something you have plugged into one of those receptacles in an always-hot socket.  If you put an ammeter between these "hot" neutrals and the connected one, it would tell you what they draw.  

The 3-way theory doesn't hold.  Since black is always-hot, the other two would have to be messengers.  The two messengers would have to go down another cable that is 3 wires, so that could only be the other /3.  There would be a lot more wire-nuts in there, and there's be no way for switched hot power to make it to any other receptacle.  

Wiring methods

The people who wired this were hacks.   Using both backstabs and screws because you're too lazy to pigtail is appalling and illegal.   It is possible to put 2 wires on/under the same screw, but you need to use products auch as Leviton's screw-and-clamp system, which are designed and listed for that.  A commercial grade Leviton receptacle with that system is under $3.  Never use screws and backstabs.  Never use backstabs in any case. 

If you don't want to use the Leviton or competitor system, just pigtail as you see the black was pigtailed.  Get some wire nuts and short lengths of wire.  You can buy 2 feet of 12/3 cable and cut it apart to get wires.  

That may be #14 (not #12) wire, it probably was if they were using backstabs, most stabs won't take #12.  12 is a universal choice, but stiffer. 

If I were you I would think about replacing every receptacle in the house.  They probably backstabbed a lot of it, very common for builders in a hurry, also using the cheap 60 cent receptacles and switches.   At least get rid of the stabs, they are bad news.