Did you not see this?
Yes, I did. "404" = "page cannot be displayed" or page cannot be found.
So then I used structure /index.php/%year%/%monthnum%/%day%/%postname%/
and put in the new rewrite rules in htaccess. Then when I went to the blog I got Internal Server Error.
There should be no rewrite rules generated by that structure. Did you not see step 2?
So I guess if you use permalinks you cannot use Archive and Category links.
No, not true. There are plenty of use using permalinks with working archive and category links.
Let's start from the beginning. Use FTP to access the directory which houses both index.php, /wp-admin/, /wp-content/, etc. If there is a .htaccess file there, set its permissions to 666 (CHMOD 666). More info: http://codex.wordpress.org/Changing_File_Permissions
Now, go to Options/Permalinks. Let the category base blank and enter this (and only this) in the structure field:
Now, hit the update button. If you correctly set .htaccess' permissions to 666, there should be no rewrite rules to enter. WordPress should have automatically updated the .htaccess file for you.
If you were entering the rewrite rules into any .htaccess file other than the one mentioned above, delete them now. They are in the wrong .htaccess file and probably the source of all these problems. Now, before continuing, please re-read this post starting from "Let's start from the beginning." Once you have finished that, you may begin.