The best way to solve your problem would be, if VLC could generate a playlist with all your music in it, while shuffle is enabled. Then you would just add that playlist to your startup items and would be done.
Unfortunately I don’t know much about VLC, but as far as I can see, a saved playlist looses the shuffle option. Maybe that’s something you can change in the preferences, but there are workarounds. One is done manually. The other one in fact it involves Automator. For both ways you need a playlist. So create it and save it whereever you like. Then:
1) Manually
Add the playlist to your startup items (for example in System Preferences go to the accounts option, select the startup items tab and add the playlist there). Now at each login the playlist will be loaded by the default player (VLC - if not, do a get-info on the playlist and change it there), but shuffle is not enabled. Solution:
Click the shuffle icon in VLC.
2) Automated
Fire up Automator and start a workflow.
a) From the list with all the actions select something like "Start application". If you can’t find it, search for application in the search-field. Drag that action to the right. Then select VLC from the action’s drop-down menu.
b) There’s a record button right on top of the automator window. You will soon press it and record your own actions. But first make sure, VLC is running.
c) Press the record button. Automator will disappear (except for a small heads-up display) and you will do something like:
• Switch to VLC
• Go to the menu File - Open File and select your playlist
• Click the shuffle icon
• Click the stop button in Automator’s heads-up display
d) Close VLC and back in Automator test your workflow by running it. If there are errors, adjust your workflow (for example add a pause action if something goes to fast). When everything is working, save your workflow and add it to your startup items.