What you are looking for is called pretty permalink. You can set it in the WordPress’s settings.
Head over to Settings > Permalinks. You will notice there are couple of options in the Common Settings section. What you want is a custom structure that isn’t available in the list. You have to add it yourself.
Add this to your custom permalink structure:
/%category%/%postname%/
So your full permalink will be like:
http://example.com/%category%/%postname%/
This will append the category, and then the post’s name to your URLs.
If you want to change the breadcrumb’s structure, you need to add its code to your question. It’s not possible to tell you how to solve it without seeing how it’s generated.
To remove the category base from your permalink, you can add this rewrite rule to your .htaccess file:
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteRule ^category/(.+)$ http://example.com/$1 [R=301,L]
</IfModule>
This will change http://example.com/category/blog to http://example.com/blog. Remember to change example.com to your site’s URL (pay attention to www)
You can also do this by installing one FV Top Level Cats or Remove Category URL plugin. Yoast also provides this.
There was a trick that would allow you to do this without installing any plugin, but it doesn’t work since version 4.6. In this trick, you would fill the category base with a period . which would remove the category word from the URL, but don’t do this. It doesn’t work anymore, and will get you into an infinite redirect.