Good day all, is there anyone that can give me a hand rebroadcasting a tx that is currently stuck? 

I sent it from a cold paper wallet that I had printed off sometime ago and used Mycelium's cold storage spend option on my android device.  We weren't in a big hurry for it to clear so we used the recommended "economy" fee.  Well this was right before there was an explosion in transactions and now the fee I used is showing that it will take "inf" (which I think means infinity) on the bitcoinfees website.

Now I still have the paper wallet with the private key, and as far as I know I just need to rebroadcast the tx with a higher fee and it should get picked up and the other rejected.  But I can't find a client that will allow me to do this as it shows the funds are currently spent. 

Can anyone give me a hand? Whats the best way to get this done?  I found a bitcoin tx booster site, but they want like 60$US to do it, which is around 3 to 5  times what the tx fee should cost for me to send it and have it mined in a day or less, so I don't really want to pay for that service which seems to be charging way more than should be.  That and I'm not entirely sure its legit either.