ASIC vs ? -- Performance & Cost
If your budget is less then 10-20 thousand dollars (or more realistically 100K+), you have no hope of getting an ASIC made.
The common device used instead of an ASIC, in situations where you cannot afford the NRE (non-returnable expenses - basically the cost for producing the masks for etching your asic, as well as the design costs), is to use a FPGA.
There is a list of papers related to using FPGAs for hash-cracking here.
A lot depends on what you mean when you say your budget is "limited". Big FPGAs can be several hundred dollars a piece, and that's just for the IC (integrated circuit)! The great majority of FPGA-based hash crackers that have been built by amateurs are done by reverse-engineering existing products from e-bay that use FPGAs, commonly real-time video encoding/processing devices.
Really, if you're serious about this project, you should spend some time researching and understanding HDLs. FPGAs (as well as ASICs) are not "programmed" in C, or any other common language you may be familliar with. Instead, they use a language (called a 'Hardware description language") that describes a series of logic operations and registers, that all operate in parallel. It's quite different then C.
Then, you should purchase an inexpensive FPGA development board (digilent makes some nice ones), and get your hashing algorithm working and tuned. Then you could look at scaling up.
It's worth noting that none of this would run linux at all. Everything ASICs do (as well as FPGAs) is so-called "bare metal" the way a ASIC/FPGA works is fundamentally different then a microcontroller, and there is no such thing as a FPGA "operating system". The extent to which linux (or any operating system) is likely to be involved is simply communicating with the special-purpose hardware and feeding it things to hash/reading back hashing hits. This would probably occur over USB, or if you're using a platform like the Zynq, through shared memory.
It's interesting that you mention the parallela people, as that's a pretty good example of the costs involved in doing a fairly complex ASIC. They needed about ~$750,000 to get their design produced as hardware.
Why not look for a generally available existing crypto IC that does what you want?
Example
family of secure authentication ICs using the SHA-256 hash algorithm with a 256-bit key length
There are development kits. Sparkfun produce a breakout for it. It communicates using I2C or 1-wire.
(caveat - I've no idea if this particular chip can be used in the way you want)
If bitcoin-mining is the objective, for $1299 75bc you can buy an ASIC-based bitcoin miner. As in all gold-rushes, the shovel sellers prosper more than 99% of the guys desperately scrabbling knee-deep in mud.
FPGAs are definitely the way to go here. I have an Atlys board ($349, $199 for students) that I use for my personal development and it's definitely suits my needs at the moment. There is even open source hashing firmware for bitmining that you might be able to hack or use as a starting point for your own firmware.
Using an atlys, you can get about 3.2 MH/s, this might work for your application. If this is for bitcoin mining, this calculator indicates you'll make 0.0001 BTC in 24 hours at the current difficulty. I looked into it a while back and it's just not worth it unless you have a much beefier board, like perhaps one with a virtex 5 FPGA on it, especially if you're a student ($995, $445 for students).
Just to note, FPGA firmware coding and normal procedural coding are worlds apart. Even if you write code in verilog, which is similar syntactically to c, you are essentially describing the hardware rather that giving a processor a list of instructions.