Assuming you have Windows Media Player, you should be able to do this pretty easily.
In Windows Media Player, click on the "Playlists" selection. Then select "Create Auto Playlist". Click on "Click here to add criteria" under any of the music libraries you see there. A list with a scroll bar will appear. At the bottom of the scroll selection, there should be an item called "more...". Click "more". Next, a new list will appear, and on it will be an item called "Randomize Playback Order". Click that. Then you will be brought back to the previous window. Now click "Click here to add criteria" again. Click "more" again. This time select "Limit total size to". Type in the total size you want. Say, 4GB or so? And lastly, save your playlist.
At this point you can edit your playlist manually if you want.
Now that you have a playlist created, save it and then click "Sync" to sync it to a portable device. Follow the instructions. I usually manually remove the files first using the Android file browser. But Windows Media Player should handle that automatically if you do the "auto sync" feature. I'm not sure if it just deletes everything first on the Android device or whether it just deletes enough to free up space. I think it's probably the former, not the latter.
Hope that helps.