You didn’t only have messed up Normals, but also double vertices:

Look at the number of Verts (bottom right). That should be16 (4 at each corner, it is only one ‘Cube’).
Select all and ALT+M, this will remove 40 Vertices and leave you with this:

Now use SHIFT+N to recalcluate the Normals (because they are not all blue) and you’re good to go. Bevel away:
